tarjan算法

• 強(qiáng)連通分量

  void tarjan(int u){
  vis[u]=true;
  LOW[u]=DFN[u]=cnt++;
  for(int v:g[u]){
      if(!DFN[v]){//沒(méi)訪問(wèn)過(guò)繼續(xù)
          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];
  }

• 縮點(diǎn)

  void tarjan(int u){
  vis[u]=true;
  LOW[u]=DFN[u]=cnt++;
  Q.push(u);//入棧
  for(int v:g[u]){
      if(!DFN[v]){//沒(méi)訪問(wèn)過(guò)繼續(xù)
          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);
  }
  */

• 割點(diǎn)

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

邊的雙連通分量定義:
若一個(gè)無(wú)向圖中的去掉任意一條邊都不會(huì)改變此圖的連通性，即不存在橋，則稱作邊雙連通圖。一個(gè)無(wú)向圖中的每一個(gè)極大邊雙連通子圖稱作此無(wú)向圖的邊雙連通分量
點(diǎn)的雙聯(lián)通分量定義:
若一個(gè)無(wú)向圖中的去掉任意一個(gè)節(jié)點(diǎn)都不會(huì)改變此圖的連通性，即不存在割點(diǎn)，則稱作點(diǎn)雙連通圖。一個(gè)無(wú)向圖中的每一個(gè)極大點(diǎn)雙連通子圖稱作此無(wú)向圖的點(diǎn)雙連通分量。

• 點(diǎn)雙

  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是割點(diǎn)標(biāo)記一下
              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;
  }