[백준] 1765 닭싸움 팀 정하기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1765
• 🔑 union, find
  • 입력으로 친구가 들어오면 서로 union
  • 원수가 들어오면 양방향 그래프로 원수 관계를 생성
  • 생성된 원수 관계 그래프를 이용해 "내 원수의 원수도 내 친구이다." 조건을 해결한다.
    • 나 → 내 원수 → 내 원수의 원수
    • 이렇게 거쳐서 (나, 내 원수의 원수)를 union

 

from collections import defaultdict

n = int(input())
m = int(input())
    
def union(a, b):
    x = find(a)
    y = find(b)
    parent[y] = x

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

parent = [i for i in range(n+1)]
E = defaultdict(list)   # 원수 그래프

for i in range(m):
    relation = input().split()
    a, b = int(relation[1]), int(relation[2])

    if relation[0] == 'F':
        union(a, b)
    else:
        E[a].append(b)
        E[b].append(a)

for k in E:             # 나
    for i in E[k]:      # 나의 원수
        for j in E[i]:  # 나의 원수의 원수
            union(k, j) # (나, 나의 원수의 원수) union

answer = set()
for i in range(1, n+1):
    answer.add(find(parent[i]))

print(len(answer))