# kruskal
Kruskal template
very well explained herehttps://techblog-history-younghunjo1.tistory.com/262
Union Find (+deadly mistake)
as mentioned in https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-4368%EB%B2%88-%EB%B3%84%EC%9E%90%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0Then, we
[백준] 4368번: 별자리 만들기
https://www.acmicpc.net/problem/4386So we are trying to find the min distance to link all the stars together. I didnt have a clue how so I headed
[프로그래머스] 섬 연결하기
https://school.programmers.co.kr/learn/courses/30/lessons/42861다리를 최소 비용으로 건설해서 모든 섬을 연결하는 문제이다.처음에는 가장 비용이 적게 드는 다리부터 하나씩 건설하되, 이미 섬끼리 다른 다리로 연결
[백준] 15591번: MooTube (Silver) (kruskal tbc)
https://www.acmicpc.net/problem/15591I thought of union find algorithm but there were mainly 2 problems1) for a node whose parent is not strictly
[자료구조] 그래프-3
가중치그래프: 간선에 비용이나 가중치가 할당된 그래프이다.1.인접행렬로 표현2.인접리스트로 표현MST란, 신장트리 중 사용된 간선들의 가중치 합이 최소인 트리를 말한다.MST를 이루기 위해서는1\. 그래프의 모든 정점들은 연결되어야 한다2\. 연결에 필요한 간선의 가중
17472: 다리 만들기 2
1h 17m알고리즘 분류를 보고 Minimum Spanning Tree와 Kruskal 알고리즘을 공부한 후에 풀었다BFS와 MST를 찾는 Kruskal 알고리즘을 이용하여 풀었다1) 일단 섬들을 구분지어주고, 2) 각 섬들마다 다른 섬들로 이동할 수 있는 최소 길이의
13-1 최소비용신장트리
간선들의 가중치를 합한 값이 최소가 되는 신장 트리 n-1개의 간선만 사용 사이클 포함 X kruskal 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 작은 간선 e를 선택(정렬된 순서대로 간선 선택) e를 신장 트리에 넣을 경우 사이클이 생기면
[BOJ] (C++) 10723 판게아 1 <Gold 3>
10723번 판게아 1조금 독특한 요구사항이 있었던 MST 문제였다.문제에서 추출할 수 있는 정보는 다음과 같다.매번 도로가 추가될 때마다 모든 도시가 서로 직간접적으로 연결선택된 도로들의 길이의 합이 최소여야 함(최소 스패닝 트리)도로가 추가될 때마다 MST를 새로
[백준 C++] 1197 최소 스패닝 트리
문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 ...