[백준,c++] 4195번 - 친구 네트워크

문제

4195번: 친구 네트워크

 

코드

#include <iostream>
#include <unordered_map>
using namespace std;

int N;
unordered_map<string, string> parent;
unordered_map<string, int> connect_cnt;

string find_parent(string x){
    if(x == parent[x]) return x;
    else return parent[x] = find_parent(parent[x]);
}

void union_parent(string a, string b){
    a = find_parent(a);
    b = find_parent(b);
    if(a > b){
        parent[a] = b;
        connect_cnt[b] += connect_cnt[a];
        connect_cnt[a] = 0;
    }
    else{
        parent[b] = a;
        connect_cnt[a] += connect_cnt[b];
        connect_cnt[b] = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T; cin>>T;
    while(T--){
        cin>>N;
        
        for(int i=0; i<N; i++){
            string a, b; cin>>a>>b;
            if(connect_cnt[a] == 0 && parent.find(a) == parent.end()){
                connect_cnt[a] = 1;
                parent[a] = a;
            }
            if(connect_cnt[b] == 0 && parent.find(b) == parent.end()){
                connect_cnt[b] = 1;
                parent[b] = b;
            }
            
            if(find_parent(a) != find_parent(b)) union_parent(a, b);
            cout<<connect_cnt[(find_parent(a))]<<'\n';
        }
        parent.clear();
        connect_cnt.clear();
    }
}

 

풀이

[백준,c++] 18116번 - 로봇 조립

위 문제랑 동일한데 해쉬를 써야 한다는 점에서 티어가 2 차이 나는 것 같습니다. 사실 크게 다를 건 없는데 말입니다.

어떤 노드가 몇 개의 자식 노드를 가지는지 찾는 문제인 유니온 파인드 문제입니다. 

자식 노드가 몇 개인지를 기록하는 배열을 생성해놓고 유니온 파인드를 통해서 부모 노드를 합칠 때, 해당 자식 노드의 개수를 갱신하는 아이디어로 해결했습니다. 해당 자식 노드의 개수가 곧 이 문제에서 요구하는 친구 네트워크의 인원 수가 되기 때문입니다.