백준 04195 - 친구 네트워크

출처 : https://www.acmicpc.net/problem/4195 

4195번: 친구 네트워크

 

고려사항

• 유니온 파인드 문제.
• map<이름, 집합번호> 를 통해 각각의 이름에 idx를 부여하여 유니온 파인드 알고리즘을 적용.
• vector<pair<루트 집합, 구성원 수>> 로 union 시에 구성원 수를 같이 업데이트 해주고 그 값을 반환하면 됨.
• 원래 유니온 파인드에서는 같은 루트를 지닌 즉, 같은 집합에 속해 있으면 어느 곳을 업데이트 해줘도
  크게 상관이 없기 때문에, 보통 23 라인부터는 else로 묶는데
  이 알고리즘으로는 같은 집합이 합쳐져서 구성원 수 변경이 없는데도, *2 가 되어버린다.
  따라서 같은 집합에 속해 있으면 바로 반환하도록 따록 else 문을 구성한다.

 

#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
int findSet(vector<pair<int, int>> &v, int set){
    if(set == v[set].first){
        return set;
    }
 
    v[set].first = findSet(v, v[set].first);
    return v[set].first;
}
 
int unionSet(vector<pair<int, int>> &v, int set1, int set2){
    int parent1 = findSet(v, set1);
    int parent2 = findSet(v, set2);
 
    if(parent1 < parent2){
        v[parent2].first = parent1;
        v[parent1].second += v[parent2].second;
        return v[parent1].second;
    }else if(parent1 > parent2){
        v[parent1].first = parent2;
        v[parent2].second += v[parent1].second;
        return v[parent2].second;
    }else{
        return v[parent1].second;
    }
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t, n, idx, set1, set2;
    string name1, name2;
 
    cin>>t;
    for(int p=0;p<t;++p){
        cin>>n;
        idx = 1;
 
        map<string, int> m;
        vector<pair<int, int>> v(1,{0,0});
        for(int i=0;i<n;++i){
            cin>>name1>>name2;
            if(m.find(name1) == m.end()){
                m[name1] = idx;
                v.push_back({idx, 1});
                set1 = idx++;
            }else{
                set1 = m[name1];
            }
 
            if(m.find(name2) == m.end()){
                m[name2] = idx;
                v.push_back({idx, 1});
                set2 = idx++;
            }else{
                set2 = m[name2];
            }
 
            cout<<unionSet(v, set1, set2)<<"\n";
        }
    }
 
    return 0;
}