[์ด์ทจ์ฝ-๊ทธ๋ํ ์ด๋ก ] ๊ฐ์ ๋ ์๋ก์ ์งํฉ ์๊ณ ๋ฆฌ์ฆ ์์ค์ฝ๋ / Python
๐ Problem Solving/์ด์ทจ์ฝ
์ ๋ ฅ ์์
6 4 # ๋ ธ๋์ ๊ฐ์ ์ ๊ฐ์
1 4 # ๋ ธ๋์ ๋ ธ๋ ์ฌ์ด์ ์ฐ๊ฒฐ ๊ด๊ณ
2 3
2 4
5 6
์ถ๋ ฅ ์์
๊ฐ ์์๊ฐ ์ํ ์งํฉ: 1 1 1 1 5 5
๋ถ๋ชจ ํ ์ด๋ธ: 1 1 1 1 5 5
import sys
input = sys.stdin.readline
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [i for i in range(v + 1)]
for _ in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
print("๊ฐ ์์๊ฐ ์ํ ์งํฉ: ", end="")
for i in range(1, v + 1):
print(find_parent(parent, i), end=" ")
print()
print("๋ถ๋ชจ ํ
์ด๋ธ: ", end="")
for i in range(1, v + 1):
print(parent[i], end=" ")
'๐ Problem Solving > ์ด์ทจ์ฝ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด์ทจ์ฝ-์ต๋จ๊ฒฝ๋ก] ์ ๋ณด / Python (0) | 2021.07.01 |
---|---|
[์ด์ทจ์ฝ-์ต๋จ ๊ฒฝ๋ก] ๊ฐ์ ๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ / Python (0) | 2021.05.19 |