Submission #8840910

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)


struct UnionFind {
    vector<int> par;

    UnionFind(int n): par(n, -1) {};
    
    void init(int n) { par.assign(n, -1); }

    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y){
        return root(x) == root(y);
    }

    bool merge(int x, int y){
        x = root(x);
        y = root(y);

        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x){
        return -par[root(x)];
    }
};



int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m; cin >> n >> m;
    ll a[m], b[m];
    rep(i, m){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        a[i]; b[i];
    }

    ll cnt_bridge = 0;
    rep(i_skip, m){
        UnionFind uf(n);
        uf.init(n);
        

        rep(i_edge, m){
            if(i_edge == i_skip) continue;
            uf.merge(a[i_edge], b[i_edge]);
        }

        reps(i_node, 1, n){
            if(uf.root(i_node) != uf.root(0)){
                cnt_bridge++;
                break;
            }
        }
    }

    cout << cnt_bridge << endl;

    return 0;
}

Submission Info

Judge Result