[1922번] 네트워크 연결

문제 출처 :

https://www.acmicpc.net/problem/1922

알고리즘 분석 :

문제 해결에 필요한 사항

1. 유니온 파인드 :: http://www.crocus.co.kr/683

2. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

유니온 파인드 개념을 알고 크루스칼 알고리즘에 대해 이해를 한다면 해결 할 수 있는 문제이다.

최소 스패닝 트리 문제 중 가장 기본적인 문제에 해당하며 간선을 오름차순으로 정렬하고

간선을 연결하였을 때 사이클이 생긴다면 그 간선은 연결하지 않고, 그 외에는 모두 간선을 연결해주어 

최소 스패닝 트리를 만들어준다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   using namespace std;   typedef struct kruskal {     int from;     int to;     int val; }KS;   vector<KS> edge;   int parent[10002]; int res;   bool comp(KS d1, KS d2) {     return d1.val < d2.val; }   // 유니온 파인드의 파인드 방식 int find(int num) {     if (num == parent[num])         return num;       return parent[num] = find(parent[num]); } int main() {     int V, E;       scanf("%d %d", &V, &E);       for (int i = 1; i <= V; i++)         parent[i] = i;       // 그래프 형성     for (int i = 0; i < E; i++)     {         KS ks;         scanf("%d %d %d", &ks.from, &ks.to, &ks.val);         edge.push_back(ks);     }       // 크루스칼 알고리즘에 의해 간선을 오름차순 정렬     sort(edge.begin(), edge.end(), comp);       // 유니온 파인드의 유니온 방식     for (int i = 0; i < E; i++)     {         int nv = find(edge[i].from);         int nw = find(edge[i].to);           if (nv == nw)             continue;           parent[nv] = nw;           res += edge[i].val;     }       printf("%d", res);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocuss