최소신장트리 문제 리스트

<<서로소집합 + 크루스칼>>

 

<기본문제>
집합의표현 - 서로소집합 기본문제 
https://www.acmicpc.net/problem/1717

바이러스 - 서로소집합 그래프 적용 기본문제
https://www.acmicpc.net/problem/2606 

상근이의 여행 - 크루스칼 개념문제 - 1분만에 풀 수 있음...
https://www.acmicpc.net/problem/9372

최소 스패닝 트리 - 크루스칼 기본문제 
https://www.acmicpc.net/problem/1197

 

<발표문제>

별자리 만들기
https://www.acmicpc.net/problem/4386

우주신과의 교감
https://www.acmicpc.net/problem/1774

행성 터널
https://www.acmicpc.net/problem/2887

 

기본문제 - 집합의 표현, 바이러스, 상근이의 여행, 최소스패닝트리

그래프와 다르게 최소신장트리의 경우 사이클이 발생하면 안되서 사이클 발생 여부를 확인하기위해서 서로소집합 알고리즘을 사용해야 합니다. 
서로소 집합 알고리즘 구현방법을 알아야 함

 

최소신장트리 크루스칼 알고리즘 비교 블로그 https://loosie.tistory.com/167

[알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로