친구 네트워크

백준 4195번: 친구 네트워크

아이디어

유니온 파인드 자료구조에 잡기술을 하나 추가한다. 원래 parent[n] == n 이면 루트 노드임을 확인하고 n을 리턴했는데 대신에 parent[n]이 음수인 경우 루트 노드임을 확인하고 n을 리턴해준다.
기본적으로 모두 -1을 가지고 있고, Union 연산시 그 음수끼리 더해서 parent[루트]에 저장한다. 나중에 find로 루트 노드를 찾고 parent에서 그 인덱스를 참조하면 집합의 원소의 개수를 알 수 있다!!

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct _DisjSet {
    int parent[1000001] = {0,};
    
    void init() {
        memset(parent, -1, sizeof(parent));
    }
    
    int find(int n) {
        if (parent[n] < 0) return n;
        return parent[n] = find(parent[n]);
    }
    
    void Union(int n1, int n2) {
        n1 = find(n1);
        n2 = find(n2);
        if (n1 == n2) return;
        parent[n1] += parent[n2];
        parent[n2] = n1;
    }
    
} DisjSet;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int F, cnt = 1;
        string s1, s2;
        map<string, int> m;
        DisjSet d;
        d.init();
        cin >> F;
        while (F--) {
            cin >> s1 >> s2;
            if (m.find(s1) == m.end()) {
                m.insert({s1, cnt++});
            }
            if (m.find(s2) == m.end()) {
                m.insert({s2, cnt++});
            }
            d.Union(m.find(s1)->second, m.find(s2)->second);
            cout << -d.parent[d.find(m.find(s1)->second)] << '\n';
        }
    }
    return 0;
}

여담

map 자료구조에서 없는걸 찾으면 set처럼 마지막 인덱스+1 ( end() )를 반환한다.