写if(low[v] == dfn[u])也是对的?
查看原帖
写if(low[v] == dfn[u])也是对的?
273637
unforgiven_virtuoso楼主2021/2/12 12:47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

vector<int> g[N];
int dfn[N], low[N], dfc, ans; bool cv[N];
void cvb_clr(int n) { fill(dfn + 1, dfn + n + 1, 0); }
int dfs_cvb(int u, int r) {
    dfn[u] = low[u] = ++dfc;
    int cnt = 0;
    for (int v : g[u]) {
        if (!dfn[v]) {
            low[u] = min(low[u], dfs_cvb(v, r));
            if (low[v] == dfn[u] && u != r) cv[u] = 1;
            if (u == r) ++cnt;
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if (u == r && cnt >= 2) cv[u] = 1;
    return low[u];
}

int n, m, u, v;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i]) dfs_cvb(i, i);
    }
    for(int i = 1; i <= n; ++i) if(cv[i]) ans++;
    cout << ans << '\n';
    for(int i = 1; i <= n; ++i){
        if(cv[i]) cout << i << " ";
    }
    return 0;
}

这个代码ac 了

2021/2/12 12:47
加载中...