关于 tarjan 求割边
  • 板块学术版
  • 楼主Harry27182SDream
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/2/8 09:01
  • 上次更新2023/10/28 09:27:25
查看原帖
关于 tarjan 求割边
376997
Harry27182SDream楼主2022/2/8 09:01

RT,蒟蒻从没写过,和割点只有大于和大于等于的区别吗,可是我这样写遇到下面这组数据会挂,求助/kel

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int v,next;
}e[200005];
int h[100005],dfn[100005],low[100005],b[100005],u,v,n,k,cnt,num;
void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=h[u];
	h[u]=cnt;
}
void tarjan(int u)
{
	dfn[u]=++cnt;
	low[u]=cnt;
	for(int i=h[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])b[i]++;
		}
		else if(low[u]>=low[v])low[u]=min(low[u],dfn[v]);
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n+k-1;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=cnt;i++)if(b[i]>=1)num++;
	printf("%d",n+k-num/2);
	return 0;
}
5 1
1 2
2 3
3 4
1 4
2 5

这组数据 num 是 0,但是显然应该是 1

2022/2/8 09:01
加载中...