4195 - 친구 네트워크

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

네트워크의 구조와 상관없이 몇 명이 존재하는 지만 확인하면 되기 때문에 서로소 집합(Disjoint Set)으로 해결할 수 있다.

사용자의 아이디가 대소문자의 최대 20자라길래 $(26+26)^{20}$ 이면 long long으로 변환하면 편하겠거니 했는 데, 서로소 집합에서 번호를 나타내려면 이름마다 번호를 하나씩 붙이는 게 나을 것 같았다.

네트워크를 만들고 합치는 것은 간단하다. root배열을 각 원소들이 속해있는 집합의 번호라고 했을 때 p번과 q번을 합치려면 아래와 같다.

int root[100001];

int find(int k){
    if(k == root[k]) return k;
    return root[k] = find(root[k]);
}

void merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q) root[q] = p;
}

네트워크에 속해있는 원소들의 수는 어떻게 세야할까. 위 코드대로라면 원소는 대충 아래와 같이 있을 것이다.

[그림 1]

화살표로 가리키는 것은 부모-자식의 관계가 아니라 집합의 번호이다. 위처럼 두 집합은 초록색 원소가 그 집합의 대표라고 할 수 있다. 그럼 집합의 개수는 초록색 원소 위에 있는 숫자라고 하자.

(q가 p에 흡수되는) 위 코드를 참고하여 두 집합을 합치면 [그림 2]와 같이 나타낼 수 있다.

[그림 2]

q의 개수를 p에 더해주고, q는 1개(나중에 다른 집합으로 옮겨질 것을 우려한다면)로 바꿔주면 된다.

나머지 원소들의 집합 번호를 바꾸지 않아도 되는 것은, 나중에 조회할 때 find(e) 를 해주면 다시 갱신되기 때문이다.

서로 다른 이름이 N개의 줄마다 2개씩 나올 수 있으므로 배열의 범위는 $2N$으로 설정했다.

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

typedef long long lld;

int root[2000001];
int counter[2000001];

int find(int k){
    if(k == root[k]) return k;
    return root[k] = find(root[k]);
}

int merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q){
        root[q] = p;
        counter[p] += counter[q];
        counter[q] = 1;
    }
    return counter[p];
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, idx1, idx2, num=1;
        scanf("%d ", &n);
        
        for(int i=1; i<=2*n; ++i){
            root[i] = i;
            counter[i] = 1;
        }
        
        map<string, int> index;
        char s[21], p[21];
        for(int i=0; i<n; ++i){
            scanf("%s %s", s, p);
            if(index.count(s)==0) index[s] = num++;
            idx1 = index[s];
            if(index.count(p)==0) index[p] = num++;
            idx2 = index[p];
            printf("%d\n", merge(idx1, idx2));
        }
    }
    return 0;
}