백준 4195 친구 네트워크 C++

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

유니온 파인드를 단순히 적용하면 TLE를 맞는 문제이다.

따라서 배열에 지속적으로 그룹의 크기를 저장해줘야 하는데, 따라서 일관성을 가지도록 union함수를 구현해줘야한다.

무조건 작은 값이 부모가 되도록 하는 것이다.

처음에는 단순하게 주석 처리된 부분으로 제출해서 TLE를 맞았다. 가장 단순하게 할 수 있는 해결법이, 쿼리를 진행하기 전에,

모든 원소에 대해서 부모 검색을 다시 수행해서 제대로 된 부모들을 찾아두는 것인데, 이 방법을 사용할 수 없다.

#include<iostream>
#include<map> //찾는 게 없으면 0반환
#include<string>
#include<algorithm>
using namespace std;
map<string, int> mp;
 
int r[200002], fcnt[200002];
 
int getParent(int a) {
    if (r[a] == a) return r[a];
    else
        return r[a] = getParent(r[a]);
}
int join(int a, int b) {
    
    a = getParent(a);
    b = getParent(b);
    if (a < b) {
        r[b] = a;
        fcnt[a] += fcnt[b];
        fcnt[b] = 1;
        return fcnt[a];
    }
    else if (a > b) {
        r[a] = b;
        fcnt[b] += fcnt[a];
        fcnt[a] = 1;
        return fcnt[b];
    }
    return fcnt[b];
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int idx = 0;
        for (int i = 0; i < 2 * n; i++) {
            r[i] = i;
            fcnt[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            string fir, sec;
            cin >> fir >> sec;
 
            if (mp.count(fir) == 0) {
                mp.insert({ fir, idx });
                idx++;
            }
            if (mp.count(sec) == 0) {
                mp.insert({ sec, idx });
                idx++;
            }
            
            cout << join(mp[fir], mp[sec]) << '\n';
            
            //for (int i = 1; i < idx; i++) getParent(i);
 
            //int cnt = 0;
            //for (int i = 0; i < idx; i++)
            //    if (r[i] == r[mp[fir]])
            //        cnt++;
            //cout << cnt << '\n';
        
        }
        mp.clear();
        
    }
    return 0;
}