알고리즘/문제풀이
[그래프] BOJ 4195 친구 네트워크
JEon.E
2023. 7. 1. 14:01
|
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
|
import sys
input = sys.stdin.readline
from collections import defaultdict
def find(parent, x):
if x != parent[x]:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, parent_cnt, a, b):
a = find(parent, a)
b = find(parent, b)
if a != b:
parent[b] = a
parent_cnt[a] += parent_cnt[b]
T = int(input())
for _ in range(T):
F = int(input())
parent = dict()
parent_cnt = defaultdict(int)
for _ in range(F):
a, b = input().split()
if not parent.get(a):
parent[a] = a
parent_cnt[a] = 1
else:
a = find(parent, a)
if not parent.get(b):
parent[b] = b
parent_cnt[b] = 1
else:
b = find(parent, b)
union(parent, parent_cnt, a, b)
print(parent_cnt[a])
|
cs |
반응형