@[DimensionTripper](/space/show?uid=55454) %%%~~感觉在群里见过你~~
by Wy12121212 @ 2018-02-10 16:50:16
@[Wy12121212](/space/show?uid=49662) 巧了，我也感觉见过你
by DimensionTripper @ 2018-02-10 16:51:56
**牛逼牛逼**
by Aoki_灏 @ 2018-02-10 16:54:13
缩点裸题咋会想不到 tarjan 呢
by qwqKanade @ 2018-02-10 17:34:04
@[v天下第柒v](/space/show?uid=50202) 我不会啊，教练的训练题考到了，然而他没讲……内心mmp
by DimensionTripper @ 2018-02-10 18:12:36
向tarjan低头 orz
```cpp
#include <bits/stdc++.h>
#define N 50010
using namespace std;
int n,m,p[N],xx,yy,cnt,st[N],top,b_size[N],dfn[N],low[N],id,num,be[N],ans,a;
bool instack[N],flag[N],f[N];
struct edge
{
int to,nxt;
};struct edge e[N];
void tarjan(int x)
{
flag[x]=1;
instack[x]=1;
st[++top]=x;
dfn[x]=++id;
low[x]=id;
int ed=p[x];
while(ed>0)
{
int k=e[ed].to;
if(!flag[k])
{
tarjan(k);
low[x]=min(low[x],low[k]);
}
else if(instack[k])
low[x]=min(low[x],low[k]);
ed=e[ed].nxt;
}
if(low[x]==dfn[x])
{
++num;
while(st[top+1]!=x)
{
be[st[top]]=num;
instack[st[top]]=0;
b_size[num]++;
top--;
}
}
}
void add(int x,int y)
{
cnt++;
e[cnt].to=y;
e[cnt].nxt=p[x];
p[x]=cnt;
}
void dfs(int x)
{
int ed=p[x];
while(ed>0)
{
if(be[x]!=be[e[ed].to])
f[be[x]]=1;
ed=e[ed].nxt;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&xx,&yy);
add(xx,yy);
}
for(int i=1;i<=n;i++)
if(!flag[i])
tarjan(i);
for(int i=1;i<=n;i++)
if(!f[be[i]])
dfs(i);
for(int i=1;i<=num;i++)
{
if(!f[i])
ans++,a=i;
if(ans>1)
{
cout<<0;
return 0;
}
}
cout<<b_size[a];
return 0;
}
```
by DimensionTripper @ 2018-02-10 19:48:07
@[DimensionTripper](/space/show?uid=55454) 你好眼熟啊T_T
by 又一夜月 @ 2018-04-08 21:15:44