玄关样例未过求助
查看原帖
玄关样例未过求助
1024143
yangjicheng2011楼主2024/12/18 21:51
#include<bits/stdc++.h>
using namespace std;
int dfn[100001];
int low[100001];
int n,m;
int dn=0;
vector<int>qp[100001];
int cnt;
int root;
bool vis[100001];
void dfs(int x){
	dn++;
	dfn[x]=low[x]=dn;
	int ch=0;
	for(int i=0;i<qp[x].size();i++){
		int loo=qp[x][i];
		if(!dfn[loo]){
			ch++;
			dfs(loo);
			low[x]=min(low[x],low[loo]);
			if(x!=root&&dfn[x]<=low[loo]){
				vis[x]=true;
				cnt++;
			}			 					
		}
		else{	
			low[x]=min(low[x],low[loo]);
		}
	}
	if(x==root&&ch>=2){
		cnt++;
		vis[x]=true;
	}				
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		qp[u].push_back(v);
		qp[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root=i;
			dfs(i);
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(vis[i]==true){
		  printf("%d\n",i);
	    }
	}
	return 0;
}
2024/12/18 21:51
加载中...