mosty.cpp

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cYES cout << "YES\n"
#define cNO cout << "NO\n"
#define ins insert
#define mas(a, n) a + 1, a + n + 1
#define lll __int128
const int MAXN = int(1e5) + 3;
const int MOD = int(1e9) + 7;
const ll INF = int(1e9) + 7;
int timer = 0;
void dfs(int v, int pr = -1){
    was[v] = 1;
    tin[v] = ++timer;
    fup[v] = tin[v];

    for (int to : g[v]){
        if (!was[to]){
            dfs(to, v);
            if (fup[to] > tin[v]){
                is_bridge(v, to);
            }
            fup[v] = min(fup[v], fup[to]);
        }
        else if (was[to] == 1 && to != pr){
            fup[to] = min(fup[to], tin[v]);
        }
    }
}

void dfs(int v, int pr = -1){
    was[v] = 1;
    tin[v] = ++timer;
    fup[v] = tin[v];
    int child = 0;

    for (int to : g[v]){
        if (!was[to]){
            child++;
            dfs(to, v);
            if (pr != -1 && fup[to] >= tin[v]){
                is_point(v);
            }
            fup[v] = min(fup[v], fup[to]);
        }
        else if (was[to] == 1 && to != pr){
            fup[to] = min(fup[to], tin[v]);
        }
    }
    if (pr == -1 && child > 1){
        is_point(v);
    }
}

int main() {
    IOS;

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; i++){
        if (!was[i])
            dfs(i, -1);
    }


    return 0;
}