[C++] 크루스칼 알고리즘

구현 원리

1. 모든 간선들의 가중치를 오름차순 정렬
2. 가중치가 가장 작은 순으로 선택해가기
3. 모든 노드의 부모 노드를 자기 자신으로 초기화
4. 간선으로 연결할 때 숫자가 작은 노드를 부모 노드로 부모 노드 갱신하기
5. 간선으로 연결하려는 노드의 부모 노드가 다르다면 사이클이 발생하지 않기 때문에 간선 연결

1. 모든 간선들의 가중치를 오름차순 정렬

간선과 가중치를 동시에 저장하기 위해서는 vector<int,pair<int,int>> 형태로 <가중치, pair<노드1,노드2>> 관리

2. 간선으로 연결하려는 노드의 연결 여부 판단

• parents 배열에 각 노드의 부모 노드 번호 삽입
• 처음에는 각 노드의 값으로 parents 초기화 ex) parents[i]=i
• 간선을 연결하면 연결한 노드의 노드 값으로 parents 갱신

➡️ 이렇게 하면 부모 노드가 같을 경우, 연결시 사이클이 생성되기 때문에 부모 노드가 다른 경우에만 연결을 허용

❗️ 부모 노드 값을 구할 때는 DFS 활용
❗️ 간선을 연결하면 부모 노드를 갱신해야하는데 이때 현재 연결한 노드의 부모를 상대 노드로 지정하는 것이 아니라 두 루트 노드 중에 큰 노드의 루트 값을 작은 루트 값으로 갱신해야 함

📌 관련 문제
🔗 [프로그래머스/C++] 섬 연결하기