📝 문제 정보#
🧐 관찰 및 접근#
- 누가 봐도 유니온파인드 스타일이다.
- 문자열을 그대로 유니온 파인드에 넣긴 곤란하니, map 혹은 dict를 이용하자.
- 유니온 파인드를 구현할 때, 합을 잘 구해줘야한다.
- 분리 집합을 포레스트 모양이라고 생각할때, 각 트리의 루트노드에서 트리의 크기를 관리할 수 있도록 하면 쉽게 구현할 수 있다.
💻 풀이#
- 코드 (C++):
void solve(){
int Q; cin >> Q;
UF.init(Q*2);
map<string, int> mp;
while(Q--){
string A, B; cin >> A >> B;
int a, b;
if(mp.find(A) == mp.end()) mp[A] = mp.size();
if(mp.find(B) == mp.end()) mp[B] = mp.size();
a = mp[A];
b = mp[B];
UF.merge(a, b);
cout << UF.cnt[UF.find(a)] << "\n";
}
}