백준 4195번 친구 네트워크(C++)

목록을 set에 저장해서 번호 부여해서 유니온 파인드

#include<map>
#include<iostream>
#include<set>
#include<vector>

using namespace std;

vector<int>parent; 

int find(int node){
    if(parent[node]<0)return node;
    
    return parent[node]=find(parent[node]);
}

int unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return abs(parent[xp]);
    
    if(parent[xp]<parent[yp]){
        parent[xp]+=parent[yp];
        parent[yp]=xp;
        return abs(parent[xp]);
    }
    else{
        parent[yp]+=parent[xp];
        parent[xp]=yp;
        return abs(parent[yp]);
    }
    
}

       
int main(){
   int t,n;
   
   cin>>t;
   while(t--){
       set<string>s;
       cin>>n;
       string a,b;
       vector<pair<string,string>>arr;
       for(int i=0;i<n;i++){
           cin>>a>>b;
           arr.push_back({a,b});
           s.insert(a);
           s.insert(b);
       }
       map<string,int>num;
       //번호 부여 
       int cnt=1;
       for(auto it=s.begin();it!=s.end();it++){
           num[*it]=cnt;cnt++;
       }
       parent.assign(s.size()+1,-1);
       
       for(int i=0;i<n;i++){
           cout<<unions(num[arr[i].first],num[arr[i].second])<<'\n';
       }
       
   }

}