1 条题解

  • 0
    @ 2025-10-25 19:11:27
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,m,cnt,p;
    vector<int>v[100005];
    int dfn[100005],low[100005];
    bool ans[100005];
    void tarjan(int x,bool root){
    	int p=0;
    	dfn[x]=low[x]=++cnt;
    	for(int i=0;i<v[x].size();i++){
    		int y=v[x][i];
    		if(!dfn[y]){
    			tarjan(y,0);
    			low[x]=min(low[x],low[y]);
    			if(low[y]>=dfn[x]&&!root) ans[x]=1;
    			if(root) p++;
    		}
    		else{
    			low[x]=min(low[x],dfn[y]);
    		}
    	}
    	if(root&&p>=2) ans[x]=1;
    	return;	
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int u,vv;
    		cin>>u>>vv;
    		v[u].push_back(vv);
    		v[vv].push_back(u);
    	}
    	for(int i=1;i<=n;i++){
    		if(!dfn[i]) tarjan(i,1);
    	}
    	int h=0;
    	for(int i=1;i<=n;i++){
    		if(ans[i]) h++;
    	}
    	cout<<h<<endl;
    	for(int i=1;i<=n;i++){
    		if(ans[i]) cout<<i<<" ";
    	}
    	return 0;
    }
    
    

    信息

    ID
    7418
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    42
    已通过
    12
    上传者