Skip to content

Instantly share code, notes, and snippets.

@inspirit941
Created April 24, 2020 06:15
Show Gist options
  • Save inspirit941/0186a52132358ec585ae3afd0fd41e1a to your computer and use it in GitHub Desktop.
Save inspirit941/0186a52132358ec585ae3afd0fd41e1a to your computer and use it in GitHub Desktop.
# -*- 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