1717. ์งํฉ์ ํํ
ยท
๐ STUDY/์๋ฃ๊ตฌ์กฐ & ์๊ณ ๋ฆฌ์ฆ
https://www.acmicpc.net/problem/1717 ๋ฌธ์ ํด์ ํฉ์งํฉ๊ณผ ๊ฐ์ ์งํฉ์ธ์ง ํ์ธํ๋ ๋ฌธ์ ๋ก ๋ถ๋ฆฌ์งํฉ(Union-Find)์ ๋ํ์ ์ธ ๋ฌธ์ ์ด๋ค. ๊ตฌํ ๋ฐฉ๋ฒ ์ด 3๋จ๊ณ๋ก ๋๋์ด ๊ตฌํ Root๋ฅผ ์ ์ฅํ ๋ฐฐ์ด ์ด๊ธฐํ Find ํจ์ ์์ฑ ๊ฐ์ Root๋ฅผ ๊ฐ์ง๊ณ ์๋์ง ํ์ธ( ๊ฐ์ ์งํฉ์ธ๊ฐ ํ์ธ) Union ํจ์ ์์ฑ ์๋ก ๋ค๋ฅธ ๋ ์งํฉ์ ํฉ์งํฉ (Root ๋ฅผ ๊ฐ๊ฒ ํจ) ์ด๋ฏธ ๊ฐ์ผ๋ฉด ํ ํ์ ์์ ์ฝ๋ # 1717 ์งํฉ์ ํํ import sys input = sys.stdin.readline def find(num:int)->int: if parent[num] == num: return num parent[num] = find(parent[num]) return parent[num] de..