The Generous BE-24 - The 2nd Meet

mail@pastecode.io avatar
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;
}