서로소 집합1

• 

  [Algorithm] 유니온 파인드(Union-Find) 그래프 알고리즘 중 Union-Find 에 대해서 공부한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 유니온 파인드(Union-Find)란? 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속해있는지 판별하는 알고리즘입니다. 그래프에서 사이클이 존재하는지 여부를 판별할 때 유용하게 사용됩니다. 유니온 파인드(Union-Find) 그림 설명 위 그림과 같이 여러개의 노드가 모두 연결되지 않고, 자기 자신만을 집합의 원소로 가질 때 모든 값이 자기 자신을 가르키도록 합니다. 그리고 표를 보면 i는 노드 번호, parent[i]는 부모 노드 번호를 의미합니다. 즉, 자기 자신이 어떤 부모에 포함되어있는지를 의미합니다. 자 이제, .. Algorithm 2022. 8. 28.