[ALGORITHM] 백준 4195 - 친구 네트워크

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

4195번: 친구 네트워크

과정

1. par배열과 idx매핑, idx부여 cnt 초기화
2. 입력받은 이름 값을 idx에 매핑하여 저장
3. 이름 값이 idx에 없으면 새로운 idx를 부여
4. 이후 weigted union find 진행

주의할 점

친구관계는 최대 10만개이므로 par배열의 최대 사이즈를 20만보다 크게 잡아야 한다.

 

코드

#include<string>
#include<iostream>
#include<map>

using namespace std;

int T;
int F;
map<string,int> idx;
int par[200002];
int cnt;

void init(){
    for(int i=0;i<200002;i++)
        par[i]=-1;
    idx.clear();
    cnt=0;
}

int find(int x){
    if(par[x] < 0)
        return x;
    return par[x] = find(par[x]);
}

int union_sn(int a, int b){
    a = find(a);
    b = find(b);

    if(a==b)
        return -1*par[a];

    else if(a < b){
        par[a]+=par[b];
        par[b]=a;
        return -1*par[a];
    }

    else{
        par[b]+=par[a];
        par[a]=b;
        return -1*par[b];
    }
}

void solution(){
    init();
    cin>>F;

    string a,b;
    int node1, node2;

    while(F--){
        cin>>a>>b;

        if(idx.find(a)==idx.end())
            idx[a]=cnt++;
            
        if(idx.find(b)==idx.end())
            idx[b]=cnt++;
        
        node1=idx[a];
        node2=idx[b];

        cout<<union_sn(node1,node2)<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>T;
    while(T--){
        solution();
    }

    return 0;
}