UVa (10147) Highways

#include <bits/stdc++.h>
using namespace std;

int parent[800];
int x[800];
int y[800];
int visited[800][800];

struct data
{
    int u,v,w;
};

int find(int x)
{
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

bool comp(data x,data y)
{
    return x.w <= y.w;
}

int give_dis(int i,int j)
{
    int a = x[i] - x[j];
    int b = y[i] - y[j];
    return a*a + b*b;
}

int main()
{
//    freopen("uva.txt", "w", stdout);
    int t,node;
    scanf("%d",&t);
    while(t--)
    {
        vector <data> graph;
        scanf("%d",&node);
        for(int i=1;i<=node;i++) scanf("%d %d",&x[i],&y[i]);
        memset(visited,false,sizeof(visited));
        for(int i=0;i<800;i++) parent[i] = i;
        int have,cc=0;
        scanf("%d",&have);
        for(int i=0;i<have;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            visited[x][y] = visited[y][x] = true;
            int u = find(x);
            int v = find(y);
            if( u != v )
            {
                parent[u] = v;
                cc++;
            }
        }
        for(int i=1;i<=node;i++)
        {
            for(int j=i+1;j<=node;j++)
            {
                int dis = give_dis(i,j);
                graph.push_back({i,j,dis});
            }
        }
        bool flag = true;
        sort(graph.begin(),graph.end(),comp);
        int len = graph.size();
        for(int i=0; i < len && cc < node-1 ;i++)
        {
            int x = graph[i].u;
            int y = graph[i].v;
            if(visited[x][y]) continue;
            int u = find(x);
            int v = find(y);
            if( u != v)
            {
                flag = false;
                parent[u] = v;
                cc++;
                printf("%d %d\n",x,y);
            }
        }
        if(flag) printf("No new highways need\n");
        if(t) puts("");
    }
    return 0;
}