[BOJ 4195] 친구 네트워크 C++

난이도: Gold 2
번호: 4195
생성일: March 2, 2023 7:14 PM
알고리즘 분류: 분리 집합, 자료 구조, 해시를 사용한 집합과 맵
알고리즘, 자료 구조: Disjoint Set, Union-find
언어: C++

4195번: 친구 네트워크

C++

// BOJ4195 친구 네트워크
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

// 이름과 인덱스를 매핑할 unordered_map
unordered_map<string, int> uMap;
// 부모 노드를 저장할 vector
vector<int> parent;
// 친구 수를 저장할 vector
vector<int> friend_num;

// 인덱스에 해당하는 노드의 루트 노드를 반환하는 함수
int getParent(int idx)
{
    // 루트 노드인 경우, 해당 노드 인덱스를 반환
    if (parent[idx] == idx)
        return idx;

    // 루트 노드가 아닌 경우, 해당 노드의 부모 노드를 재귀적으로 탐색하여 루트 노드를 반환
    return parent[idx] = getParent(parent[idx]);
}

// 인덱스가 idx1, idx2인 두 개의 노드를 연결하는 함수
void unionParent(int idx1, int idx2)
{
    int root1 = getParent(idx1);
    int root2 = getParent(idx2);

    // 두 개의 노드가 이미 같은 트리에 속한 경우, 함수를 종료
    if (root1 == root2)
        return;

    // 두 개의 노드가 서로 다른 트리에 속한 경우, 더 작은 인덱스를 가진 노드를
    // 더 큰 인덱스를 가진 노드의 자식으로 연결한다.
    if (root1 < root2)
    {
        parent[root2] = root1;
        friend_num[root1] += friend_num[root2];
    }
    else
    {
        parent[root1] = root2;
        friend_num[root2] += friend_num[root1];
    }
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        int F, idx = 0;
        cin >> F;

        // 변수 초기화
        uMap.clear();
        parent.assign(F * 2 + 1, 0);
        friend_num.assign(F * 2 + 1, 1);

        for (int i = 0; i <= F * 2; i++)
            parent[i] = i;

        int idx1, idx2;
        for (int i = 0; i < F; i++)
        {
            string name1, name2;
            cin >> name1 >> name2;

            // name1, name2가 이미 맵에 존재하는 경우, 해당 인덱스를 사용한다.
            if (uMap.count(name1) > 0)
                idx1 = uMap[name1];
            else
                idx1 = uMap[name1] = ++idx;

            if (uMap.count(name2) > 0)
                idx2 = uMap[name2];
            else
                idx2 = uMap[name2] = ++idx;

            // 두 개의 노드를 연결한다.
            unionParent(idx1, idx2);

            // 인덱스가 idx1인 노드의 루트 노드를 찾아 해당 친구 수를 출력한다.
            int target = getParent(idx1);
            cout << friend_num[target] << "\n";
        }
    }

    return (0);
}