tarjan算法

• 强连通分量

  void tarjan(int u){
  vis[u]=true;
  LOW[u]=DFN[u]=cnt++;
  for(int v:g[u]){
      if(!DFN[v]){//没访问过继续
          tarjan(v);
          LOW[u]=min(LOW[u],LOW[v]);
      }
      else if(vis[v])//还在栈中更新
      LOW[u]=min(LOW[u],DFN[v]);
  }
  ans+=DFN[u]==LOW[u];
  }

• 缩点

  void tarjan(int u){
  vis[u]=true;
  LOW[u]=DFN[u]=cnt++;
  Q.push(u);//入栈
  for(int v:g[u]){
      if(!DFN[v]){//没访问过继续
          tarjan(v);
          LOW[u]=min(LOW[u],LOW[v]);
      }
      else if(vis[v])//还在栈中更新
      LOW[u]=min(LOW[u],DFN[v]);
  }
  ans+=DFN[u]==LOW[u];
  if(DFN[u]==LOW[u]){
      int x;
      do{
          x=Q.top();
          Q.pop();
          vis[x]=0;
          num[x]=ans;
      }while(u!=x);
  }
  }
  /*
  for(int i=1;i<=n;i++){
  for(auto &v:g[i])if(G[i]!=G[v])add(i,v);
  }
  */

• 割点

  void tarjan(int u,int fa){
  int son=0;
  LOW[u]=DFN[u]=cnt++;
  for(int v:g[u]){
      if(!DFN[v]){
          tarjan(v);
          son++;
          LOW[u]=min(LOW[u],LOW[v]);
          if(u==root&&son>1||(u!=root&&LOW[v]>=DFN[u]))ge[u]++;
      }
      else if(v^fa)
      LOW[u]=min(LOW[u],DFN[v]);
  }
  }

• 割边(桥)

  void tarjan(int u,int fa){
  LOW[u]=DFN[u]=cnt++;
  for(int v:g[u]){
      if(!DFN[v]){
          tarjan(v,u);
          LOW[u]=min(LOW[u],LOW[v]);
          if(LOW[v]>DFN[u]){
              bri.push_back({u,v});
          }
      }
      else if(v^fa)
      LOW[u]=min(LOW[u],DFN[v]);
  }
  }

边的双连通分量定义:
若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在桥，则称作边双连通图。一个无向图中的每一个极大边双连通子图称作此无向图的边双连通分量
点的双联通分量定义:
若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。

• 点双

  void tarjan(int u,int fa){
  DFN[u] = LOW[u] = cnt++;
  int son = 0;
  for(auto &v:g[u]){
      edge e = edge(u, v);
      if(!DFN[v]){
          Q.push(e);
          tarjan(v, u);
          LOW[u] = min(LOW[u], LOW[v]);
          son++;
          if(LOW[v]>=DFN[u]){
              iscut[u] = true;//u是割点标记一下
              bcc_cut++;
              cut[bcc_cut].clear();
              while(true){
                  edge x = Q.top();
                  Q.pop();
                  if(vis_cut[x.u]!=bcc_cut){
                      cut[bcc_cut].push_back(x.u);
                      vis_cut[x.u] = bcc_cut;
                  }
                  if (vis_cut[x.v] != bcc_cut){
                      cut[bcc_cut].push_back(x.v);
                      vis_cut[x.v] = bcc_cut;
                  }
                  if(x.u^u and x.v^v)break;
              }
          }
      }else if(v^fa&&DFN[v]<DFN[u]){
          Q.push(e);
          LOW[u] = min(LOW[u], DFN[v]);
      }
  }
  if(fa<0&&son==1)iscut[u]=false;
  }