首页 > 代码库 > BZOJ1051
BZOJ1051
强连通。
若只存在一个强连通分量出度为0(树根,万人敬仰),答案就是这个强连通的节点数。
若存在多个,答案即为0
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define min(x,y) (x<y?x:y)
struct
mod{
int
x,y,next;};
mod q[50015];
int
len=0,id=0,tp=0,num=0;
int
first[10015];
int
dfn[10015];
int
low[10015];
int
home[10015];
int
size[10015];
bool
vis[10015];
int
sta[10015];
int
in[10015];
int
out[10015];
void
ins(
int
x,
int
y)
{
len++;
q[len].x=x;
q[len].y=y;
q[len].next=first[x];
first[x]=len;
}
void
dfs(
int
x)
{
dfn[x]=low[x]=++id;
vis[x]=
true
;
sta[++tp]=x;
for
(
int
i=first[x];i!=0;i=q[i].next)
{
int
y=q[i].y;
if
(dfn[y]==-1)
{
dfs(y);
low[x]=min(low[x],low[y]);
}
else
{
if
(vis[y]==
true
)
low[x]=min(low[x],dfn[y]);
}
}
if
(low[x]==dfn[x])
{
num++;
while
(1)
{
int
i=sta[tp--];
vis[i]=
false
;
home[i]=num;
size[num]++;
if
(i==x)
break
;
}
}
}
int
main()
{
int
n,m;
scanf
(
"%d%d"
,&n,&m);
for
(
int
i=1;i<=m;i++)
{
int
x,y;
scanf
(
"%d%d"
,&x,&y);
ins(x,y);
}
memset
(dfn,-1,
sizeof
(dfn));
memset
(low,0,
sizeof
(low));
memset
(size,0,
sizeof
(size));
for
(
int
i=1;i<=n;i++)
if
(dfn[i]==-1)
dfs(i);
int
ans=0;
for
(
int
i=1;i<=m;i++)
{
if
(home[q[i].x]!=home[q[i].y])
in[home[q[i].y]]++,out[home[q[i].x]]++;
}
for
(
int
i=1;i<=num;i++)
{
if
(out[i]==0&&in[i]!=0)
ans+=size[i];
}
printf
(
"%d\n"
,ans);
}
BZOJ1051
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。