求割点

板子

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define dec(i,a,b) for(ll i=(a);i>=(b);i--)
#define pll pair<ll,ll>
using namespace std;
ll INF = 0x7f7f7f7f7f7f7f7f;
const int N = 5e5 + 5;
ll mod = 1e9;

ll n, m;
ll dfn[100005], low[100005], tot, res;
bool fg[100005];
vector<ll> g[100005];

void Tarjan(ll x, ll fa) {
    low[x] = dfn[x] = ++tot;
    ll child = 0;
    for (auto to : g[x]) {
        if (!dfn[to]) {
            child++;
            Tarjan(to, x);
            low[x] = min(low[x], low[to]);
            if (fa != x && low[to] >= dfn[x]) {
                fg[x] = 1;
            }
        }
        else if (to != fa) {
            low[x] = min(low[x], dfn[to]);
        }
    }
    if (child >= 2 && fa == x) {
        fg[x] = 1;
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    rep(i, 1, m) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rep(i, 1, n) {
        if (!dfn[i]) {
            tot = 0;
            Tarjan(i, i);
        }
    }
    rep(i, 1, n)
        if (fg[i])
            res++;
    cout << res << '\n';
    rep(i, 1, n) {
        if (fg[i])
            cout << i << ' ';
    }
    return 0;
}

 

上一篇:CF Divan and Kostomuksha


下一篇:sping中配置json的各种问题