社区讨论

求助B3609 [图论与代数结构 701] 强连通分量orz

学术版参与者 2已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@ltu17c45
此快照首次捕获于
2024/03/16 19:55
2 年前
此快照最后确认于
2024/03/16 21:41
2 年前
查看原帖
CPP
样例过了全WA
求HACK+解析
拜托了
本蒟蒻图论弱,大佬轻喷
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int tim,cnt,siz[N],dfn[N];
int e[N],ne[N],h[N],low[N];
int idx,id[N],d,dout[N],n,m;
int instk[N],stk[N],top;
void tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	stk[++top]=u,instk[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instk[v]==1)
		{		}
			low[u]=min(low[u],dfn[v]);

	}
	if(dfn[u]==low[u])
	{
		int y;
		cnt++;
		do{
			y=stk[top--];
			instk[y]=0;
			siz[cnt]++;
			id[y]=cnt;
		}while(y!=u);
	}
}
void add(int u,int v)
{
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
int bz[N];
int main()
{
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		{
			tarjan(i);
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++)
	{
		if(bz[i]==0)
		{
			for(int j=1;j<=n;j++)
			{
				if(id[i]==id[j])
				{
					printf("%d ",j);
					bz[j]=1;
				}
			}
			puts("");
		}
	}
	return 0;
}

回复

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

正在加载回复...