使用Tarjan算法,在求解桥的代码中加入求解割点代码,全错!!!
查看原帖
使用Tarjan算法,在求解桥的代码中加入求解割点代码,全错!!!
286752
h1910819075楼主2021/4/15 12:30

求助,各位大佬,帮帮我看看我的代码哪里出现了问题了吗?谢谢,万分感谢。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100;
int dfn[N],low[N],vis[N];
vector<int> G[N];
stack<int> s;
int n,m,num,cnt;
struct node{
	int a,b;
}bridge[N];
int point[N];
int tot=0;

inline void Tarjan(int x,int fa)
{
	num++;
	dfn[x]=low[x]=num;
	vis[x]=1;
	s.push(x);
	
	int child=0;
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(dfn[y]==0)
		{
			Tarjan(y,x);
			low[x]=min(low[x],low[y]);
			
			if(low[y]>=dfn[x]&&fa!=x)
				point[x]=1;
				
			/*if(low[y]>dfn[x])//求桥步骤 
			{
				int a=x,b=y;
				if(a>b) swap(a,b);
				bridge[++tot].a=a,bridge[tot].b=b;
			}*/
			
			if(x==fa) child++;
		}
		else if(dfn[y]<dfn[x]&&y!=fa)
			low[x]=min(low[x],dfn[y]);
	}
	if(child>=2&&fa==x) point[x]=1;
	vis[x]=0;
}

inline bool cmp(node s1,node s2)
{
	if(s1.a==s2.a)
		return s1.b<s2.b;
	else
		return s1.a<s2.a;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			Tarjan(i,-1);
	
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(point[i]) cnt++;
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		if(point[i])
			printf("%d ",i);
	printf("\n");
	
	/*sort(bridge+1,bridge+1+tot,cmp);//这里是求解桥的,请忽略。 
	for(int i=1;i<=tot;i++)
		printf("%d %d \n",bridge[i].a,bridge[i].b);*/
	return 0;
}
2021/4/15 12:30
加载中...