提到Tarjan算法就不得不提一提Tarjan这位老人家
Robert Tarjan，计算机科学家，以LCA、强连通分量等算法闻名。他拥有丰富的商业工作经验，1985年开始任教于普林斯顿大学。Tarjan于1986年获得图灵奖。并于1994年当选为ACM院士。
Tarjan其他奖项包括： 奈望林纳奖信息科学（1983第一个获奖者） 国家科学院的研究倡议奖 （1984） 巴黎Kanellakis奖-理论与实践（ ACM1999） 帕斯卡奖章数学与计算机科学（ 欧洲科学院2004） 加州理工学院杰出校友奖（ 美国加州技术研究所2010）
综上所述————Tarjan太强辣！
不扯**了，接下来让我们进入正题
Tarjan求强联通分量算法顾名思义，可以用来求强联通分量(这不是废话吗)，同时它还可以用来缩点。所谓缩点，就是将一个强联通分量糅合成一个点，然后将强联通分量里每个个点的信息都整合到这个点里，形成一个超级点
如图所示，1、2、3、4是一个强连通分量，4和5自己是一个强连通分量，那么我们就可以把这张图变成下边这张图
例题
- 板子题，没什么好说的，直接上代码
#include#include #include #include using namespace std;int read(){ int k=0; char c=getchar(); for(;c<'0'||c>'9';) c=getchar(); for(;c>='0'&&c<='9';c=getchar()) k=(k<<3)+(k<<1)+c-48; return k;}struct zzz{ int t,nex;}e[50001*2]; int head[10001],tot;inline void add(int x,int y){ e[++tot].t=y; e[tot].nex=head[x]; head[x]=tot;}int dfn[10001],deep,low[10001],vis[10001],s[100001],tail;int col,colnum[10001],belong[10001];//Tarjan缩点主体void tarjan(int f){ dfn[f]=low[f]=++deep; s[++tail]=f; vis[f]=1; for(int i=head[f];i;i=e[i].nex){ int to=e[i].t; if(!dfn[to]){ tarjan(to); low[f]=min(low[f],low[to]); } else{ if(vis[to]) low[f]=min(low[f],dfn[to]); } } if(dfn[f]==low[f]){ col++; int v=0; do { v=s[tail--]; vis[v]=0; colnum[col]++; belong[v]=col; }while(v!=f); }}int ans;int main(){ int n=read(),m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); add(x,y); } for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++) if(colnum[i]>1) ans++; cout<