백준 4195 친구 네트워크 - 파이썬

문제.

풀이.

유니온 파인드를 이용해서 풀면 된다.

입력이 문자열이기때문에 딕셔너리를 통해서 풀었다.

2개의 딕셔너리를 선언하고

number 딕셔너리의 루트 노드에 친구 관계의 친구관계의 수를 저장하고

매 단계 루트노드를 출력하면된다.

 

소스코드.

	import sys
	def union(a, b):
	a = find(a)
	b = find(b)
	if a != b:
	parent[b] = a
	number[a] += number[b]
	def find(target):
	if target == parent[target]:
	return target
	# 경로 압축
	parent[target] = find(parent[target])
	return parent[target]
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 6)
	tc = int(input())
	for i in range(tc):
	f = int(input())
	parent = {}
	number = {}
	for j in range(f):
	f1, f2 = map(str, input().split())
	if f1 not in parent:
	parent[f1] = f1
	number[f1] = 1
	if f2 not in parent:
	parent[f2] = f2
	number[f2] = 1
	union(f1, f2)
	print(number[find(f1)])

view raw 친구 네트워크.py hosted with ❤ by GitHub