[POJ] 1751 Highways.cpp

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point{
    int x;
    int y;
}P[751];
struct Edge{
    int A;
    int B;
    double Len;
}E[751*751];

int Set[751];

void Set_Initial(const int &N);
int Find_Root(const int &x);
void Union(int x, int y);
bool Union(const Edge &E);
bool cmp(const Edge &A, const Edge &B) {
    return A.Len < B.Len;
}
int main()
{
    int N, M;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; ++i)
            scanf("%d %d", &P[i].x, &P[i].y);

        int nOfE = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = i + 1; j <= N; ++j) {
                E[nOfE].A = i;
                E[nOfE].B = j;
                E[nOfE++].Len = sqrt(pow(P[i].x-P[j].x, 2) + pow(P[i].y - P[j].y, 2));
            }
        sort(E, E + nOfE, cmp);

        Set_Initial(N);

        int A, B;
        scanf("%d", &M);
        for (int i = 0; i < M; ++i) {
            scanf("%d %d", &A, &B);
            Union(A, B);
        }

        for (int i = 0; i < nOfE; ++i) {
            if (Union(E[i])) {
                printf("%d %d\n", E[i].A, E[i].B);
            }
        }
    }
}
void Set_Initial(const int &N)
{
    for (int i = 1; i <= N; ++i)
        Set[i] = i;
}
int Find_Root(const int &x)
{
    if (x == Set[x])
        return x;
    return Set[x] = Find_Root(Set[x]);
}
void Union(int x, int y)
{
    x = Find_Root(x);
    y = Find_Root(y);

    if (x != y)
        Set[x] = y;
}
bool Union(const Edge &E)
{
    int x = Find_Root(E.A);
    int y = Find_Root(E.B);

    if (x != y) {
        Set[x] = y;
        return true;
    }
    return false;
}