Created
April 24, 2020 06:15
-
-
Save inspirit941/0186a52132358ec585ae3afd0fd41e1a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
# UTF-8 encoding when using korean | |
import sys | |
def find_parent(x, parent): | |
if x not in parent or x == parent[x]: | |
return x | |
p = find_parent(parent[x], parent) | |
parent[x] = p | |
return p | |
def union_find(x, y, parent): | |
x = find_parent(x, parent) | |
y = find_parent(y, parent) | |
if x != y: | |
parent[y] = x | |
n, m = map(int, sys.stdin.readline().split()) | |
parent = dict() | |
for _ in range(m): | |
a, b = map(int, sys.stdin.readline().split()) | |
# a, b 오름차순으로 변경 | |
if b < a: | |
a, b = b, a | |
# a 학생 기준으로 그룹화 | |
union_find(a, b, parent) | |
print(len(set(find_parent(i, parent) for i in range(1, n+1)))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment