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;
  }