[백준 4195] 친구 네트워크

[백준 4195] 친구 네트워크

문제 링크

using namespace std;
int T, F;
int parent[2000001];
int num[2000001];
int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
int merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x != y) {
        parent[y] = x;
        num[x] += num[y];
        num[y] = 1;
    }

    return num[x];
}
void input() {
    cin >> T;
    for(int t=0; t<T; t++) {
        cin >> F;
        map<string, int> m; // 친구 네트워크 번호
        int cnt = 1;

        for(int i=1; i<=F; i++) {
            parent[i] = i;
            num[i] = 1;
        }

        for(int i=0; i<F; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            if(!find(m[s1])) {
                m[s1] = cnt++;
            }

            if(!find(m[s2])) {
                m[s2] = cnt++;
            }

            int first = m[s1];
            int second = m[s2];
            cout << merge(first, second) << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    return 0;
}

• union find로 푸는 문제. 시간 초과때문에 애좀 먹었다.
• 맨 처음에는 union find가 아니라 그냥 맵으로 구현 했는데, 시간 초과가 나서 union find로 풀었다.
• 맵에는 친구 네트워크의 번호를 저장 해 놓는다.
• 해당 친구 네트워크의 번호를 merge로 판별 해 같다면 그냥 리턴하고, 같지 않다면 합쳐준다.