[문제 링크] : https://www.acmicpc.net/problem/4195
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<string, int> M;
unordered_map<string, string> U;
string solve(string s){
if(U[s] == s){
return s;
}
else{
return U[s] = solve(U[s]);
}
}
void uni(string a, string b){
string ta = solve(a);
string tb = solve(b);
if(ta == tb){
return;
}
U[tb] = ta;
M[ta] += M[tb];
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T, N;
cin >> T;
string a, b;
while(T--){
cin >> N;
M.clear();
U.clear();
for(int i=0; i<N; i++){
cin >> a >> b;
if(U.find(a) == U.end()){
U.insert({a, a});
M.insert({a, 1});
}
if(U.find(b) == U.end()){
U.insert({b, b});
M.insert({b, 1});
}
uni(a, b);
cout << M[solve(a)] << "\n";
}
}
return 0;
}
'알고리즘' 카테고리의 다른 글
[알고리즘] 백준 14697 - 방 배정하기 (C++) (0) | 2024.09.13 |
---|---|
[알고리즘] 백준 5052 - 전화번호 목록 (C++) (0) | 2024.09.12 |
[알고리즘] 백준 20006 - 랭킹전 대기열 (C++) (0) | 2024.09.10 |
[알고리즘] 백준 30802 - 웰컴 키트 (C++) (0) | 2024.09.09 |
[알고리즘] 백준 11328 - Strfry (C++) (0) | 2024.09.08 |