2606 바이러스 python

https://www.acmicpc.net/problem/2606

2606번: 바이러스

1번을 제외한 모든 감염된 컴퓨터

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

1번을 제외한 감염된 컴퓨터의 수를 출력하면 된다.

dfs, bfs로도 구현이 되지만 union and find로 구현했다.

https://portable-paper.tistory.com/entry/Union-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Union & Find 알고리즘

필요한 함수

union: 합치기

find: 부모찾기

checkParent: 부모가 1인지 확인하기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
2606
union find로 구현하면 바로 풀릴듯
"""

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y: parent[y] = x
    else: parent[x] = y

N = int(input())
pair_count = int(input())
parent = [i for i in range(1, N+1)]

for i in range(pair_count):
    a, b = map(int,input().split())
    union(a, b)

print(parent.count(1))

30616KB 40ms