codeground 최소 신장 트리

Codeground 최소 신장 트리 https://www.codeground.org/practice/practiceProblemView

중간 간선(N/2번째 간선)이 가장 최소값인 신장 트리를 만들었을 때 그 값을 구하는 문제이다. 

즉, 최소 신장 트리를 구하는 문제이다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int N, M;     vector<pair<int, pair<int, int> > > adj; vector<int> par; int find(int x){     if (x == par[x]) return x;     else return par[x] = find(par[x]); } bool merge(int a, int b){     a = find(a);     b = find(b);     if (a == b) return false;     par[b] = a;     return true; } int main(){     setbuf(stdout, NULL);     int T;     scanf("%d", &T);     for (int t = 1; t <= T; t++){         scanf("%d%d", &N, &M);         adj = vector<pair<int, pair<int, int> > >();         par = vector<int>(N + 1);         for (int m = 0; m < M; m++){             int u, v, d;             scanf("%d%d%d", &u, &v, &d);             adj.push_back(make_pair(d,make_pair(u, v)));        //가중치 간선         }         for (int n = 1; n <= N; n++) par[n] = n;         sort(adj.begin(), adj.end());         int ans, cnt = 0;         for (int n = 0; n < adj.size(); ++n){             if (merge(adj[n].second.first, adj[n].second.second)){                 cnt++;                 if (cnt == N / 2)                     ans = adj[n].first;                 else if (cnt == N - 1)                     break;             }         }         printf("Case #%d\n", t);         printf("%d\n", ans);     }     return 0; } Colored by Color Scripter

cs