补一下之前学的
这些代码都是一样的
POJ2186（英文版） = OpenJ_Bailian - 2186（英文版） = 计蒜客T2956（中文） = LibreOJ10091（中文）
学习视频链接
https://www.bilibili.com/video/av60380978?p=1
（可以看视频画的图）
关键点
最最最重要的就是dfn和low这两个数组
dfn[x]：x点DFS到的时间（即时间戳），（注意：记录的是首次搜索到的序号）（记录被搜索到的先后次序）。
low[x]：x点及其后代指出去的边 能返回到的最浅的点的时间戳。 --> （因为如果x能搜索到比自己小的时间戳的点，那么就说明形成了一个环）
scc[x]：表示x属于哪一个强连通。
如果一个点没有指出去的边了，（不能往下了，不能指向更浅的地方了，所以指向它自己），说明该点是一个强连通分量。
当x点的dfn[x] = low[x]，说明以x为根的子树（该点及其后代）是一个强连通分量
思路
DFS+栈维护
栈：维护一个SCC中有哪些点
时间复杂度：(O(V+E))
图的存储算法
这个模板用的是邻接表，还可以学一下下面这些：
邻接矩阵 数组表示
邻接表 链表表示 主要是有向图
十字链表 链表表示 主要是有向图
邻接多重表 链表表示 主要是无向图
AC代码：
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<list>
#include<stdlib.h>
#include<map>
#include<stack>
#include<stdio.h>
#include<queue>
using namespace std;
typedef long long ll;
#define sc(T) scanf("%d",&T)
#define scc(x,y) scanf("%d %d",&x,&y)
#define pr(T) printf("%d
",T)
#define f(a,b,c) for (int a=b;a<=c;a++)
#define ff(a,b,c) for (int a=b;a>=c;a--)
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define PI acos(-1)
const int N=1e4+20;
const int M=5e4+20;
int n,m,num,id,tot=0,top;
int head[N],de[N],si[N],scc[N],st[N];
int dfn[N],low[N];
struct node
{
int nex,v;
}e[M];
void add(int u,int v)
{
e[++tot].nex=head[u];
head[u]=tot;
e[tot].v=v;
}
void tarjan(int u) //tarjan缩点
{
if(dfn[u])
return; //说明被搜到过/访问到过
dfn[u]=low[u]=++id; //id记录访问到的序号 （序号一直在增加的）
st[++top]=u;//入栈 记录该点之后的子树是有哪些和它一起构成scc的
for(int i=head[u];i!=-1;i=e[i].nex) // 遍历这个点连出去的边
{
int v=e[i].v;
if(!dfn[v]) //如果该点未访问过
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]) //如果还在栈内
low[u]=min(low[u],dfn[v]); //更新low数组 为什么更新：需要去找到low数组维护的该点指出去的最小的时间戳（dfn值）
}
// 该节点所连的边全部遍历完之后 （无法走去其他点 （有向图））
// 判断是否是scc，不是的话该函数走完，是的话开始回溯找到该节点所连接的点构成一个scc
if(low[u]==dfn[u]) //这个根组成的是不是一个scc 如果后代不能找到更浅的点
{
// 相等的话就是一个强联通分量
// 那么以该点点为根的就是一个scc
scc[u]=++num; //num是scc的个数
++si[num];
while(st[top]!=u) // 从栈中弹出节点，一直到是u节点为止 因为以它为根是一个scc
{
++si[num];
scc[st[top--]]=num; //找到 st栈 数组 弹出
}
--top;
// num++;
// for(;;)
// {
// int x=st[top--];
// scc[x]=num;
// if(x==u)
// break;
// }
}
}
int main()
{
while(~scc(n,m))
{
mem(head,-1);
mem(dfn,0);
mem(scc,0);
for(int i=1;i<=m;i++)
{
int x,y;
scc(x,y);
add(y,x);//反向建边
}
for(int i=1;i<=n;i++)
tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=head[i];j!=-1;j=e[j].nex)
{
if(scc[i]!=scc[e[j].v])
{
de[scc[e[j].v]]++;
}
}
}
int ans=0,u=0;
for(int i=1;i<=num;i++)
{
if(!de[i])
{
ans=si[i];
u++;
}
}
if(u==1)
pr(ans);
else
pr(0);
}
return 0;
}