알고리즘

[알고리즘] 백준 4195 - 친구 네트워크 (C++)

blueberrysoda 2024. 9. 11. 22:56

[문제 링크] : 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;
}