【模板】强连通分量

概念

1. 什么是强连通？
   • 在有向图中，的最大环的个数
2. 有什么作用?
   • 有向图的缩点

算法思路

1. tarjan算法dfs图。
2. 每次dfs的时候都更新最小时间戳和dfs序。
3. 用栈记录dfs的所有的节点
4. 如果某个节点dfs跑完他的子图后，最小时间戳没有更新，那么，他跑的后续的节点都是在他这个环上，给这些点打上标记，并记录是第几个环。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+12,M=2e5+12;
struct {
  int to,nex;
}edge[M];
stack<int>s;
int n,m;
int dfn[N],used[N],vis[N],low[N],color[N],num[N];
int colornum,cnt,ans,cnt2,head[N];
void addedge(int u,int v)
{
  cnt2++;
  edge[cnt2]={v,head[u]};
  head[u]=cnt2;
}
void paint(int x) //打上标记，记录是第几个环
{
  s.pop();
  color[x]=colornum;
  num[colornum]++;
  vis[x]=0; //这个点已经进入其他环了，后续不能使用这个点
}
void tarjan(int x)  //tarjan算法跑图
{
  dfn[x]=low[x]=++cnt; //赋初值
  s.push(x);   //遍历过的点，都进入栈里面
  vis[x]=1;   //这个点在栈里面，可以用它更新其他的点的值。
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( !dfn[y] )
    {
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if( vis[y] ) low[x]=min(low[x],dfn[y]);
  }
  if( low[x]==dfn[x] )
  {
    colornum++;
    while( s.top()!=x )
    {
      int t=s.top();
      paint(t);
    }
    paint(x);
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int u,v;
    scanf("%d%d",&u,&v);
    addedge(u,v);
  }
  for(int i=1;i<=n;i++)
  {
    if( !dfn[i] ) tarjan(i);
  }
  for(int i=1;i<=colornum;i++)
  {
    if( num[i]>1 ) ans++;
  }
  printf("%d",ans);
}