tose33

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net kruskal 로 mst 만들면 된다. mst 가 만들어지는 조건은 ( 간선의 갯수 = 노드의 갯수 - 1 ). kruskal 을 돌렸는데 위 조건이 만족되지 않는다면 -1 출력한다.

https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net mst를 만들고, mst 에 선택되지 않은 간선의 합이 답이다.

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 크루스칼로 mst 를 만들면 되는데 조금 다르다. 이 문제에서는 발전소가 있는 노드가 있고, 모든 마을은 단 하나의 발전소에만 연결되어야 한다. 따라서 여러개의 mst 가 만들어진다. 해결방법은 union 가능 여부를 크루스칼 알고리즘에서는 부모 노드가 다르면 union 가능하다고 보는데, 이 문제에서는 부모를 발전소로하고, 두 노드의 부모를 비교해서 부..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 내림차순 정렬후 크루스칼 알고리즘. 오름차순 정렬후 크루스칼 알고리즘. 총 두번 돌려주면 되는 문제.