10661번: Median Tree

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

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e3, MAX_M = 1e4;
int n, m, flag[MAX_N + 1];
struct edge {
    int s, t, c;
    bool operator<(edge i) const {
        return c < i.c;
    }
}e[MAX_M];
int f(int x) {
    if (x == flag[x]) return x;
    return flag[x] = f(flag[x]);
}
int main() {
    for (;;) {
        scanf("%d %d", &n, &m);
        if (!n&&!m) break;
        for (int i = 0; i < m; i++)
            scanf("%d %d %d", &e[i].s, &e[i].t, &e[i].c);
        sort(e, e + m);
        for (int i = 1; i <= n; i++) flag[i] = i;
        int cnt = 0, ra, rb;
        for (int i = 0; i < m; i++) {
            ra = f(e[i].s);
            rb = f(e[i].t);
            if (ra == rb) continue;
            if (ra > rb) swap(ra, rb);
            flag[rb] = ra;
            if (++cnt == n / 2) {
                printf("%d\n", e[i].c);
                break;
            }
        }
    }
    return 0;
}