서로소 집합을 활용한 사이클 판별
📌서로소 집합을 활용한 사이클 판별서로소 집합은 무방향 그래프 내에서의 사이클 판별할 때 사용(방향 그래프 내에서의 사이클 판별은 DFS 사용) 1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다. - 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다 - 루트 노드가 서로 같다면 사이클이 발생한 것이다.2. 그래프에 포함되어 있는 모든 간선에 대해 1번을 반복한다. 📌코드# 특정 원소가 속한 집합 찾기def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return pare..
코딩테스트
2024. 11. 10. 19:42