호지

최소 스패닝 트리 문제를 크루스칼 알고리즘을 적용하여 풀었다. find_root는 연결된 최상위 노드를 찾는 함수이다. union_root는 연결할 2개의 노드가 최상위노드가 다르면 같게 바꿔주는 함수이다. 간선과 가중치에 대한 정보를 edge vector에 저장하고 가중치 기준으로 sort한 후, edge벡터를 탐색함으로 가중치가 최소인 최소스패닝트리를 구할 수 있다.(그리디 알고리즘) #include #include #include using namespace std; vector edge; vector parent; int find_root(int x){ if(parent[x] == x) return x; else return parent[x] = find_root(parent[x]); } void..