JUNGOL 1813 - 종교 with Python

대표적인 Union-Find 문제다. UnionFind 관련해서는 해당 사이트가 진짜 잘 설명해준 것 같다. 물론 파이썬은 아니지만 알고리즘만 이해한다면 구현은 어렵지 않아서 이 사이트를 읽고 풀어보는걸 추천한다. Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 서로 같은 그래프에 속하는지 판단하는 그래프 알고리즘. 이름 그대로 union 연산과 find 연산이 존재 union(a, b) : a와 b가 포함되어 있는 집합을 합치는 연산 find(x) : x가 어떤 집합에 포함되어 있는지 찾는 연산 시뮬레이션 모든 노드(정점)은 자기 자신을... zoosso.tistory.com import sys input = sys.stdin.readl...

원문링크 : JUNGOL 1813 - 종교 with Python