Submission #8843812

---

Source Code Expand

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


class UnionFind {
public:
    std::vector<int> data;
    UnionFind( int n ) {
        data.resize( n, -1 );
    }
    int find( int x ) {
        if ( data[x] < 0 ) {
            return x;
        } else {
            int r = find( data[x] );
            data[x] = r;
            return r;
        }
    }
    void unite( int x, int y ) {
        int r = find( x );
        int s = find( y );
        if ( r != s ) {
            data[r] += data[s];
            data[s] = r;
        }
    }
};

ll solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M);
    for ( int i = 0; i < M; i++ ) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    }
    ll ans = 0;
    for ( int i = 0; i < M; i++ ) {
        UnionFind uf(N);
        for ( int j = 0; j < M; j++ ) {
            if ( j == i ) continue;
            uf.unite(A[j], B[j]);
        }
        int v = uf.find(0);
        if ( -uf.data[v] != N ) ans++;
    }

    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result