社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...