社区讨论

萌新刚学tarjan,请求大佬帮助!!!

P3388【模板】割点(割顶)参与者 5已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@mi7w4eiq
此快照首次捕获于
2025/11/21 04:35
4 个月前
此快照最后确认于
2025/11/21 06:32
4 个月前
查看原帖
样例未过!!!
CPP
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define MAXN 20100
#define MAXM 101000

struct node
{
	int u,v,next;
}edge[MAXM];
int n,m,x,y,ans,index,cnt;
int head[MAXN],LOW[MAXN],DFN[MAXN],a[MAXN];

void add_edge(int u,int v)
{
	edge[++cnt].next=head[u];
	edge[cnt].u=u;
	edge[cnt].v=v;
	head[u]=cnt;
}

void tarjan(int x,int rt)
{
	//printf("%d %d\n",x,rt);
	int tot=0;
	LOW[x]=DFN[x]=++index;
	for (int i = head[x] ; i ; i = edge[i].next)
	{
		int v=edge[i].v;
		if(!DFN[v])
		{
			tarjan(v,rt);
			LOW[x]=min(LOW[x],LOW[v]);
			if(x!=rt&&DFN[x]<=LOW[v]) a[i]=1;
			if(x==rt) ++tot;
		}
		LOW[x]=min(LOW[x],DFN[v]);
	}
	if(tot>=2&&x==rt) a[rt]=1;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1 ; i <= m ; ++ i)
	{
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	for (int i = 1 ; i <= n ; ++ i)
	{
		if(!DFN[i]) tarjan(i,i);
	}
	for (int i = 1 ; i <= n ; ++ i)
	{
		if(a[i]) ++ans;
	}
	printf("%d\n",ans);
	for (int i = 1 ; i <= n ; ++ i)
	{
		if(a[i]) printf("%d ",i);
	}
	return 0;
}

回复

15 条回复,欢迎继续交流。

正在加载回复...