«   2022/10   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Archives
Today
0
Total
96,326
관리 메뉴

차근차근

[백준 4195] 친구 네트워크 본문

대학교/Algorithm

[백준 4195] 친구 네트워크

SWKo 2020. 2. 22. 18:09

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. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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<stringint> 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;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1065] 한수  (0) 2020.02.23
[백준 1922] 네트워크 연결  (0) 2020.02.23
[백준 1010] 다리 놓기  (0) 2020.02.21
[백준 4948] 베르트랑 공준  (0) 2020.02.20
[백준 1197] 최소 스패닝 트리  (0) 2020.02.19
0 Comments
댓글쓰기 폼