92pts蒟蒻求助
查看原帖
92pts蒟蒻求助
1277550
cx2021hjxhjx楼主2024/7/15 09:37

rt

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,root,tot,ans[100010],flag[100010],low[100010],dfn[100010],x,y,sum;
vector<int>e[200010];
void dfs(int cur,int father){
    int child=0;
	dfn[cur]=low[cur]=++tot;
    for(int i=0;i<e[cur].size();i++){
        int u=e[cur][i];
        if(u){
            if(!dfn[u]){
                child++;
                dfs(u,cur);
                low[cur]=min(low[cur],low[u]);
                if(cur!=root&&low[u]>=dfn[cur]) flag[cur]=1;
                if(cur==root&&child>=2) flag[u]=1;
            }
			else if(u!=father) low[cur]=min(low[cur],dfn[u]);
        }
    }
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
    	root=i;
        if(!dfn[i]) dfs(i,root);
	}
    for(int i=1;i<=n;i++){
        if(flag[i]){
            cnt++;
            ans[++sum]=i;
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=sum;i++) cout<<ans[i]<<" ";
    return 0;
}
2024/7/15 09:37
加载中...