[BOJ] #4195 - 친구 네트워크

4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net ** 문제 유형 해시, 집합, 네트워크 ** 풀이 해시를 활용한 Union-Find(합집합 찾기) 알고리즘을 이용해 문제 해결 파이썬 - dictionary 자료형을 해시처럼 사용 +) Union-Find 알고리즘 원소들의 연결 여부를 확인하는 알고리즘 원소가 어느 부분 집합에 포함되어 있는지 알 수 있음 # 원소가 포함되어 있는 부분집합의 부모(대표자) 찾기 def find(x): if x == parent[x]: return x else: p = ..

2021.06.13