# The Generous BE-24 - The 2nd Meet

unknown
c_cpp
a year ago
1.9 kB
3
Indexable
Never
```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class UnionFind {
vector<int> parent;
public:
int numSets;
UnionFind(int size) {
parent.resize(size);
for(int i = 0; i < size; i++) parent[i] = i;
numSets = size;
}

int findSet(int i) {
if(parent[i] == i) return i;
return parent[i] = findSet(parent[i]);
}

bool isSameSet(int i, int j) {
return findSet(i) == findSet(j);
}

void unionSet(int i, int j) {
int x = findSet(i), y = findSet(j);
if(x == y) return;

numSets--;
if(y < x) swap(x, y);
parent[y] = x;
}
};

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int V, E; cin >> V >> E;
UnionFind uf(V);
vector<pair<int, int>> bridges;
for(int i = 0; i < E; i++) {
int a, b; cin >> a >> b;
a--; b--;
if(b < a) swap(a, b);
bridges.push_back({a, b});
}

sort(bridges.begin(), bridges.end());

for(auto x : bridges) {
uf.unionSet(x.first, x.second);
}

int ans = 0;
vector<pair<int, int>> newBridges;
for(int i = 1; i < V; i++) {
if(!uf.isSameSet(0, i)) {
uf.unionSet(0, i);
ans += (i + 2);
newBridges.push_back({1, i + 1});
}
}

cout << newBridges.size() << ' ' << ans << '\n';
for(int i = 0; i < newBridges.size(); i++) {
if(newBridges[i].second > newBridges[i].first) swap(newBridges[i].first, newBridges[i].second);
}
sort(newBridges.begin(), newBridges.end(), greater<pair<int, int>>());
for(auto x : newBridges) {
cout << x.first << ' ' << x.second << '\n';
}

return 0;
}
```