uvaSolutions/uva-10147.cpp at master · fatemehkarimi/uvaSolutions · GitHub

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//uva 10147
//Highways

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>

using namespace std;

double dis(pair <int, int> a, pair <int, int> b);
void DFS(vector < vector <int> > & Graph, vector <int> & visited, int start, int code);
void Union(vector <int> & ufds, int a, int b);
int parent(vector <int> & ufds, int a);

int main(void)
{
    int T = 0;
    cin >> T;
    while(T--){
        int n;
        cin >> n;

        vector <pair <int, int> > cities(n);

        for(int i = 0; i < n; ++i)
            cin >> cities[i].first >> cities[i].second;

        int e;
        cin >> e;

        vector <vector <int> > Graph(n);

        for(int i = 0; i < e; ++i){
            int u, v;
            cin >> u >> v;

            --u, --v;

            Graph[u].push_back(v);
            Graph[v].push_back(u);
        }

        vector <int> connected_components(n, -1);
        int region = 0;

        for(int i = 0; i < n; ++i)
            if(connected_components[i] == -1)
                DFS(Graph, connected_components, i, region++);

        set < pair <double, pair <int, int> > > kruskalSet;
        map < pair <double, pair <int, int> >, pair <int, int> > realEdges;//inter component edges to inter node edges

        for(int i = 0; i < n; ++i)
            for(int j = i + 1; j < n; ++j){
                int u = connected_components[i];
                int v = connected_components[j];
                if(u != v){
                    double dst = dis(cities[i], cities[j]);
                    kruskalSet.insert(make_pair(dst, make_pair(u, v)));
                    realEdges[make_pair(dst, make_pair(u, v))] = make_pair(i, j);
                }
            }

        vector <pair <int, int> > added_highways;
        vector <int> ufds(region);
        for(int i = 0; i < region; ++i)
            ufds[i] = i;

        bool no_new_highway = 1;

        while(!kruskalSet.empty()){//connected_component is used as the set for kruskal algorithm
            auto edge = *kruskalSet.begin();
            int u = edge.second.first;
            int v = edge.second.second;

            kruskalSet.erase(kruskalSet.begin());

            if(parent(ufds, u) != parent(ufds, v)){
                Union(ufds, u, v);

                no_new_highway = 0;
                added_highways.push_back(realEdges[edge]);

            }
        }

        if(no_new_highway)
            cout << "No new highways need" << endl;
        else
            for(auto edge : added_highways)
                cout << edge.first + 1 << ' ' << edge.second + 1 << endl;

        if(T) cout << endl;
    }

    return 0;
}

void Union(vector <int> & ufds, int a, int b)
{
    int p1 = parent(ufds, a);
    int p2 = parent(ufds, b);

    ufds[p2] = p1;

    return;
}

int parent(vector <int> & ufds, int a)
{
    int x = a;
    while(x != ufds[x])
        x = ufds[x];

    while(a != ufds[a]){
        int tmp = ufds[a];
        ufds[a] = x;
        a = tmp;
    }

    return x;
}

double dis(pair <int, int> a, pair <int, int> b)
{
    int tmp = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
    return sqrt(tmp);
}

void DFS(vector < vector <int> > & Graph, vector <int> & visited, int start, int code)
{
    visited[start] = code;

    for(auto a : Graph[start])
        if(visited[a] == -1)
            DFS(Graph, visited, a, code);

    return;
}