반응형

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

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 rel 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. unordered_map 자료 구조를 활용하여 해당 친구의 인덱스를 저장합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 rel 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<unordered_map>
#include<string>
 
using namespace std;
 
int vect[200001];
int rel[200001];
unordered_map<string, int> m;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
    rel[pa] += rel[pb];
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int F;
        int cnt = 1;
        m.clear();
        scanf("%d", &F);
 
        for (int i = 1; i <= F * 2; i++) {
            vect[i] = i;
            rel[i] = 1;
        }
 
        for (int i = 0; i < F; i++) {
            char A[21];
            char B[21];
            scanf("%s %s", A, B);
 
            if (m.count(A) == 0) {
                m[A] = cnt++;
            }
            if (m.count(B) == 0) {
                m[B] = cnt++;
            }
 
            int a = m[A];
            int b = m[B];
 
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
 
            printf("%d\n", rel[Find(a)]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27

+ Recent posts

티스토리툴바