有dalao帮我看看我这个无向图割边的问题啊,老是多输出一个错的
  • 板块学术版
  • 楼主2_6HogCycle
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/11/13 20:24
  • 上次更新2023/11/4 00:40:38
查看原帖
有dalao帮我看看我这个无向图割边的问题啊,老是多输出一个错的
524782
2_6HogCycle楼主2021/11/13 20:24
#include<iostream>
#include<cstring>
using namespace std;
struct edge{
	int to;
	int next;
}edge[100000];
int index,head[1001],q,n,m,cnt;
int a,b;
int low[10001],book[100001],num[100001];
void dfs(int cur,int fa)
{
	low[cur]=num[cur]=++index;	
	for(int i=head[cur];i;i=edge[i].next)
	{		
		int v=edge[i].to;
		if(v==fa)
			continue;
		if(!num[v])
		{
			dfs(v,cur);
			low[cur]=min(low[v],low[cur]);
			if(low[v]>num[cur])
				cout<<cur<<"----"<<v<<"是割边"<<endl;	
		}
		else low[cur]=min(num[v],low[cur]); 
	}
}
void star(int u,int v) 
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int main()
{
	cin>>n>>m;
	cnt=1;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		star(a,b);
		star(b,a);
	}
	dfs(1,1);
	return 0;
 } 
2021/11/13 20:24
加载中...