WA了最后一个点,求调,谢谢各位巨佬
查看原帖
WA了最后一个点,求调,谢谢各位巨佬
355521
rainbow_star楼主2021/11/7 19:17
//tarjan无向图求割点和桥 
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
const ll N=20001;
ll n,m;//n个点,m条边
struct NODE
{
	ll to;
	ll num;
}l;
vector<NODE> road[N];
ll u,v;
ll ans;
ll dfn[N],low[N];
//dfn[i]表示节点i被访问到的时间点
//low[i]表示节点i通过有向边可回溯到的最早的时间点
ll t;//当前时间戳分配到t了
ll fa[N];
bool gd[N];
//bool bridge[N];
void dfs(ll now) 
{
	t++;
	low[now]=dfn[now]=t;
	ll i;
	ll child=0;
	for(i=0;i<road[now].size();i++) 
	{
		if(dfn[road[now][i].to]==0) 
		{ 
			//没有被访问过
			child++;
			fa[road[now][i].to]=now;
			dfs(road[now][i].to);
			if(fa[now]==0&&child>=2)
			{
				if(gd[now]==false)
				{
					gd[now]=true;
					ans++;
				}
			}
			if(fa[now]!=0&&low[road[now][i].to]>=dfn[now])
			{
				if(gd[now]==false)
				{
					gd[now]=true;
					ans++;
				}
			}
//			if(low[road[now][i].to]>dfn[now])
//				bridge[road[now][i].num]=true;
			low[now]=min(low[now],low[road[now][i].to]);
		} 
		else if(road[now][i].to!=fa[now])
			low[now]=min(low[now],low[road[now][i].to]);
	}
}
int main() 
{
	ll i;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;i++) 
	{
		scanf("%lld%lld",&u,&v);
		l.num=i;
		l.to=v;
		road[u].push_back(l);
		l.to=u;
		road[v].push_back(l);
	}
	for(i=1;i<=n;i++) 
	{
		if(dfn[i]==0)
			dfs(i);
	}
	printf("%lld\n",ans);
	for(i=1;i<=n;i++)
	{
		if(gd[i]==true)
			printf("%lld ",i);
	}
	return 0;
}
2021/11/7 19:17
加载中...