[백준 4195] 친구 네트워크

0. 제목

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

---

1. 문제

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

---

2. 풀이

• 서로소 집합(Disjoint Set)으로 해결할 수 있다.
• Union-find 방식을 사용한다.
• 기존 union방식과는 다르게 각 집합에 포함에 있는 원소 개수를 구하고 반환해준다.
• key값과 value값을 쌍으로 사용하는 map 을 사용한다.
• num을 통해 노드번호를 부여한다.
• 처음에는 시간초과가 떴지만 ios_base~cin 이 부분으로 속도를 향상시켜주어서 정답처리가 되었다.

---

3. 코드

#include <iostream>
#include <map>
using namespace std;
 
int parent[2000001];
int counter[2000001];
 
//root를 찾는 함수
int find(int x){
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}
 
//두 집합을 합치는 함수
int merge(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v){//같은 집합에 있지 않다면
        parent[v] = u;//두 집합을 연결
        counter[u] += counter[v];//v개수를 u에 더해줌
        counter[v] = 1;//v가 나중에 다른 곳에서 쓰일 수 있으니 1로 초기화 시켜줌
    }
    return counter[u];
}
 
int main(int argc, const char * argv[]){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int T;
    cin >> T;
    for(int i = 0; i < T; i++){
        int F;
        cin >> F;
        
        for(int j = 1; j <= 2*F; j++){
            parent[j] = j;
            counter[j] = 1;
        }
        
        map<string, int> index;//map은 key값과 value값이 pair를 이루고 있다.
        string u, v;
        int idx1, idx2;
        int num = 1;
        for(int j = 0; j < F; j++){
            cin >> u >> v;
            if(index.count(u) == 0) index[u] = num++;//u에 num을 통해 노드번호를 부여
            idx1 = index[u];//u에 해당하는 value를 idx1에 저장
            if(index.count(v) == 0) index[v] = num++;//v에 num을 통해 노드번호를 부여
            idx2 = index[v];//v에 해당하는 value를 idx2에 저장
            cout << merge(idx1, idx2) << '\n';
        }
    }
    return 0;
}