90分蒟蒻求助 少输出两个数
查看原帖
90分蒟蒻求助 少输出两个数
238108
appIestar334楼主2022/5/19 12:20

90分 第11个点 少了中间两个答案(??)害怕

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m,ver[N],head[N],Next[N],tot,dfn[N],low[N],pd[N];
bool cu[N];
int num;
vector<int>key;
inline void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void dfs(int p,int fa){
	low[p]=dfn[p]=++num;
	int child=0;
	for(int i=head[p];i;i=Next[i]){
		int y=ver[i];
		if(!dfn[y]){
			dfs(y,fa);
			low[p]=min(low[p],low[y]);
			if(low[y]>=dfn[p]&&p!=fa) cu[p]=1;
			if(p==fa)++child;
		}
		low[p]=min(low[p],dfn[y]);
	}
	if(child>=2&&p==fa) cu[p]=1;
}
int main(){
//	freopen("P3388_1.in","r",stdin);
//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;++i)if(!dfn[i]) dfs(i,i);
	for(int i=1;i<=n;++i)if(cu[i]) key.push_back(i);
	cout<<key.size()<<endl;
	for(int i=0;i<key.size();++i) cout<<key[i]<<' ';
	return 0;
}
2022/5/19 12:20
加载中...