[백준] 4195.친구 네트워크(c++)

4195.친구 네트워크

🔑문제 유형

union-find 
입력값에 대해 부모에 대한 정보를 재귀적으로 찾고 부모가 다르면 하나의 부모를 보도록 수정.

🛠 시행 착오

런타임 에러 (OutOfBounds) : 정보 담는 갯수 2*n 
시간초과 : ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

📃 코드

#include <iostream>
#include <map>
using namespace std;

int parent[200001];
int cnt[200001];

//넘어온 자식 idx에 대한 최상위 부모 idx 리턴하는 함수
int find(int idx){

    //자기 자신이 부모라면
    if(idx==parent[idx]) return idx;
    else{
        parent[idx] = find(parent[idx]);
        return parent[idx];
    }
}

int merge(int f1,int f2){

    //각자 부모 찾기
    int pf1 = find(f1);
    int pf2 = find(f2);

    //둘이 부모 다르면 한쪽으로 몰아주기
    if(pf1!=pf2){
        cnt[pf1]+=cnt[pf2];
        cnt[pf2]=1;
        parent[pf2]=pf1;
    }
    
    return cnt[pf1];
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;

    while(T--){
        //string-idx 매핑 맵
        map<string,int> m;
        int n=0,idx=0,rs=0;
        cin>>n;

        //네트워크 갯수(1),부모 idx 초기화(자기 자신)
        //f1,f2 한줄이 두명의 정보이기 때문에 *2 해줘야함
        for(int i=0; i<n*2; i++)
        {
            cnt[i]=1;
            parent[i]=i;
        }

        for(int i=0; i<n; i++)
        {
            string f1,f2;
            cin>>f1;
            cin>>f2;

            //idx 부여
            if(!m.count(f1)) m[f1]=idx++;
            if(!m.count(f2))m[f2]=idx++;

            rs = merge(m[f1], m[f2]);
            cout<<rs<<"\n";
        }

    }
    return 0;
}