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

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

 

 

알고리즘 종류

부분 집합

자료 구조

 

 

 

사고 과정

부분 집합을 할 parents 배열을 만듭니다. 그리고 몇 명이 연결되어 있는지 기록할 state라는 배열을 만듭니다. 이후 union_find으로 해결하면 됩니다.

 

 

 

구현(C++)

#include <iostream>
#include <string>
#include <map>
#include <vector>
#define endl "\n"
 
using namespace std;
 
 
int tc, n;
 
map<string, int> m;
int parents[200001];
int state[200001];
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
 
void union_parents(int a, int b){
 
    a = get_parent(a);
    b = get_parent(b);
 
    if(a>b){
        parents[a] = b;
        
        int tmp = state[b];
        state[b] += state[a];
        state[a] += tmp;
    }
    else{
        parents[b] = a;
        
        int tmp = state[a];
        state[a] += state[b];
        state[b] += tmp;
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);    
    cin >> tc;
    
    for(int t=0; t<tc; t++){
        
        cin >> n;
 
        for(int i=0; i<200001; i++){
            parents[i] = i;
            state[i] = 1;
        }
        
        m.clear();
        int num=1;
        string s1, s2;
        
        for(int i=0; i<n; i++){
            cin >> s1 >> s2;
            
            if(m[s1] == 0) m[s1] = num ++;
            if(m[s2] == 0) m[s2] = num ++;
            
            int a = get_parent(m[s1]);
            int b = get_parent(m[s2]);
            
            if(a != b) union_parents(a, b);
 
            cout << max(state[a], state[b]) << endl;                                                   
        }
    }
}

 

 

 

 

시행착오