문제풀이/그래프
[파이썬] [그래프] 백준 4195 친구 네트워크
승무_
2022. 3. 29. 17:44
문제
https://www.acmicpc.net/problem/4195
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
코드
from sys import stdin
input = stdin.readline
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
parent[b] = a
number[a] += number[b]
print(number[a])
for _ in range(int(input())):
num = int(input())
parent, number = {}, {}
for i in range(num):
a, b = input().split()
if a not in parent:
parent[a] = a
number[a] = 1
if b not in parent:
parent[b] =b
number[b] = 1
union(a, b)