tarjan无向图割点标程求助
查看原帖
tarjan无向图割点标程求助
269085
Iceturky楼主2023/7/13 20:01
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long

using namespace std;

int read()
{
	int w,f=1;char c;
	while((c=getchar())>'9'||c<'0')
		if(c=='-')f=-1;
	w=c-'0';
	while((c=getchar())>='0'&&c<='9')
		w=w*10+c-'0';
	return w*f;
}

const int N=2e4+5,M=1e5+5;

struct node{
	int v,nxt;
}p[2*M];
int head[N],tott;
void add(int u,int v){p[++tott]={v,head[u]},head[u]=tott;}


int a[N],f[N];
int num[N];

int dfn[N],low[N],tot,cnt;
bool vis[N],cut[N];
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	int ch=0;
	bool tag=0;
	for(int i=head[u];i;i=p[i].nxt)
	{
		int v=p[i].v;
		if(v==fa)
			continue;
		if(!dfn[v])
		{
			tarjan(v,u);
			ch++;
			low[u]=min(low[u],low[v]);
		}
		else
			low[u]=min(low[u],dfn[v]);
		tag|=low[v]>=dfn[u];
	}
	if((fa!=0&&tag)||(fa==0&&ch>=2))
		cut[u]=1,cnt++;
}

int n,m;

signed main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		if(u==v)
			m--,i--;
		else
			add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,0);
	printf("%lld\n",cnt);
	for(int i=1;i<=n;i++)
		if(cut[i])
			printf("%lld ",i);
	printf("\n");
	return 0;
}

是这样的

tarjan里面的for循环最后一句放在了外面

然后WA了

放在if语句里就A了

不是很懂

2023/7/13 20:01
加载中...