백준 4195 친구 네트워크 - map과 union-find 혼합 문제

문제 링크

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

풀이 아이디어

줄이 n개일때 최대 2n명의 인물이 나올 수 있음을 인지하고 초기화를 진행하자.

이름을 map의 key로 저장(파이썬에서는 딕셔너리)하고, value로는 각자 고유한 숫자 값을 저장한다.

후에 이 value가 union find를 할 때 node의 index값이 될 것이다.

 

편의상 앞에 나오는 녀석이 parent가 된다고 가정하고, union을 진행할 때

자식 노드의 친구 개수가 부모 노드의 친구 개수와 합쳐지면서

자식 노드의 친구 개수는 1로 줄여야 함을 잊지 말자.

find를 통해 부모 노드의 친구 개수와 합쳐지는 구조이므로 반드시 1로! 줄여야 함.

 

코드

#include <bits/stdc++.h>
using namespace std;

int t,f;
int root[200002];
int num[200002];
int find(int x){
    if(x==root[x]) return x;
    else return root[x]=find(root[x]);
}

int un(int x,int y){
    x = find(x);
    y = find(y);
    if(x!=y) {
        root[y] = x;
        num[x] += num[y];
        num[y]=1;
    }
    return num[x];
}

int main(void){
    cin>>t;
    while(t--){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin>>f;
        map<string,int> fmap;
        string name1,name2;
        int idx=0;
        int a,b;
        for(int i=0; i<f*2; i++){
            root[i]=i;
            num[i]=1;
        }
        for(int i=0; i<f;i++){
            cin>>name1>>name2;
            if(fmap.count(name1)==0)
                fmap[name1]=idx++;
            a=fmap[name1];
            if(fmap.count(name2)==0)
                fmap[name2]=idx++;
            b=fmap[name2];
            cout<<un(a,b)<<"\n";
        }
    }
}