1 条题解

  • -15
    @ 2023-8-19 16:06:16
    #include<bits/stdc++.h>
    using namespace std;
    int n,m;
    vector<int>a[100005];
    int dfn[100005],low[100005],times,cnt[100005],sum;
    void dfs(int u,int Root){
    	int child=0;
    	dfn[u]=low[u]=++times;
    	for(int i=0;i<a[u].size();i++){
    		int v=a[u][i];
    		if(dfn[v]==0){
    			child++;
    			dfs(v,Root);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>=dfn[u]&&u!=Root)cnt[u]=1;
    		}else low[u]=min(low[u],dfn[v]);
    	}
    	if(u==Root&&child>1)cnt[u]=1;
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int u,v;
    		cin>>u>>v;
    		a[u].push_back(v);
    		a[v].push_back(u);
    	}
    	for(int i=1;i<=n;i++){
    		if(!dfn[i])dfs(i,i);
    	}
    	for(int i=1;i<=n;i++){
    		if(cnt[i])sum++;	
    	}
    	cout<<sum<<endl;
    	for(int i=1;i<=n;i++){
    		if(cnt[i])cout<<i<<' ';
    	}
    	return 0;
    }
    
    

    信息

    ID
    487
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    308
    已通过
    86
    上传者