Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.3 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using db = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<db, db>;
using tiii = tuple<int, int, int>;
using str = string;

#define vt vector
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

constexpr int maxN = 100000;

vt<int> graph[maxN], h(maxN), f(maxN);
vt<bool> used1(maxN, false);
set<pii> bridges;

void dfs1(int u, int p = -1) {
    used1[u] = true;
    h[u] = f[u] = (p == -1 ? 0 : h[p] + 1);
    for (int &g : graph[u]) {
        if (g != p) {
            if (used1[g]) {
                f[u] = min(f[u], h[g]);
            } else {
                dfs1(g, u);
                f[u] = min(f[u], f[g]);
                if (h[u] < f[g]) {
                    bridges.ins({u, g});
                    bridges.ins({g, u});
                }
            }
        }
    }
}

vt<bool> used2(maxN, false);
vt<int> nums(maxN);

void dfs2(int u) {
    used2[u] = true;
    for (int &g : graph[u]) {
        if (!used2[g] && !bridges.count({u, g})) {
            nums[g] = nums[u];
            dfs2(g);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    dfs1(0);
    int st = 0;
    for (int i = 0; i < n; i++) {
        if (!used2[i]) {
            nums[i] = st++;
            dfs2(i);
        }
    }
    vt<int> p(st);
    for (pii b : bridges) {
        int cmp1 = nums[b.fi], cmp2 = nums[b.se];
        p[cmp1]++;
        p[cmp2]++;
    }
    int cnt = 0;
    for (int i = 0; i < st; i++) {
        if (p[i] == 2) cnt++;
    }
    cout << (cnt + 1) / 2;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}