친구 네트워크 4195

문제

접근 방법

문자열이 입력으로 주어지기에 Map같은 해시를 사용하여 숫자로 변환해주고 유니온 파인드를 하면 된다. 루트 집합에 몇 명이 속한지 저장해주고 다른 집합과 합칠 때 넘겨주거나 넘겨받으면 된다.

코드

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int friendAmount[200001], parents[200001], groupIdx;
unordered_map<string, int> stringMap;
int find(int num)
{
    if (parents[num] == num)
        return num;
    return parents[num] = find(parents[num]);
}
void merge(int num1, int num2)
{
    num1 = find(num1);
    num2 = find(num2);
    if (num1 > num2)
    {
        parents[num2] = num1;
        friendAmount[num1] += friendAmount[num2];
    }
    else if (num2 > num1)
    {
        parents[num1] = num2;
        friendAmount[num2] += friendAmount[num1];
    }
}
int stringToInt(string str)
{
    int num;
    if (stringMap.count(str) == 0)
    {
        num = groupIdx++;
        stringMap[str] = num;
    }
    else
    {
        num = stringMap[str];
    }
    return num;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T, F, n1, n2;
    string f1, f2;
    cin >> T;
    for (int i = 0; i < 200001; ++i)
    {
        parents[i] = i;
        friendAmount[i] = 1;
    }
    while (T--)
    {
        stringMap.clear();
        cin >> F;
        for (int i = 0; i <= groupIdx; ++i)
        {
            parents[i] = i;
            friendAmount[i] = 1;
        }
                groupIdx = 0;
        while (F--)
        {
            cin >> f1 >> f2;
            n1 = stringToInt(f1);
            n2 = stringToInt(f2);
            merge(n1, n2);
            cout << friendAmount[find(n1)] << "\n";
        }
    }
    return 0;
}

풀이

반례도 다 맞았는데 5%에서 틀려서 이해가 안 됐다.
여러 가지를 확인해보다 parents와 friendAmount를 초기화하는 과정을 잘못했음을 알게 됐다.
200,000까지 가야 하는데 100,000까지만 초기화를 해줘서 틀렸다.
해당 부분을 수정해주니, 해결됐다.
찾아보니 F의 2배만큼 초기화해주는 방법도 존재한다.

기본적인 부분에서 실수해버려서 좀 아쉬웠다.