백준 4195 친구 네트워크(python, Union-Find)

* 문제 링크: https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

* 해결 방법: Union-find

1. 사람 수를 100,000명까지 입력 가능하지만, 완탐으로 풀면 시간초과. 따라서, 집합을 이용하여 해결

2. 비어있는 dict 하나를 구성

3. 입력받은 name1과 name2가 dict에 존재하지 않으면, 각 name을 key값으로 잡고 0번 인덱스부터 차근차근 저장

4. 집합을 구성할 arr=[-1] * (2*n+2) #사람 수가 2명씩 입력되기 때문에 *2를 했음

5. union(dict[name1], dict[name2]) 진행 후, 마지막에 연산된 arr[a] 값 리턴

import sys def find(x):     if arr[x] < 0:         return x     arr[x] = find(arr[x])     return arr[x] def union(x,y):     a, b = find(x), find(y)     if (a!=b):         arr[a] += arr[b]         arr[b] = a     return arr[a] test_case = int(input()) for test in range(test_case):     n = int(input())     names = {} #이름     cnt = 0 # 사람 수     arr = [-1] * (2*n+2)     for i in range(n):         f1, f2 = sys.stdin.readline().rstrip().split()         if f1 not in names:             names[f1] = cnt             cnt += 1         if f2 not in names:             names[f2] = cnt             cnt += 1         print(-1 * union(names[f1], names[f2]))