tarjan連通分量總結

這個東西怎麼說呢，感覺很丢臉啊，高中就學過的東西，現在作為一個打了兩年比賽的ACMer，居然對這個東西不太熟。

tarjan算法我就不說了。連通分量的概念我也不說了。現在看來tarjan主要用于三個方面。首先按照無向圖和有向圖去分類。

在有向圖裡面，由于圖是有向的，是以可以研究的東西沒有那麼多。如果能夠找到從a到b的路徑，也能夠找到從b到a的路徑，那麼這兩個點就在同一個強連通分量裡面。求有向圖強連通分量，直接就是最樸素的tarjan算法。這裡還是給出模闆吧，其他幾個tarjan的用法就在這個模闆的基礎上修改。

inline void tarjan(int x)
{
  low[x]=dfn[x]=++dindex;
  v[x]=true; sta.push(x);
  for(int i=0;i<g[x].size();i++)
  {
    int y=g[x][i];
    if (!dfn[y])    
    {
      tarjan(y); low[x]=min(low[x],low[y]);
      
    } else if (v[y]) low[x]=min(low[x],dfn[y]);
  }
  if (dfn[x]==low[x])
  {
    cnt++; int j=0;
    do
    {
      j=sta.top();sta.pop();
      v[j]=0; belong[j]=cnt;        //belong[j]表示j屬于的連通塊的編号
    } while (j!=x);
  }
}      

下面考慮無向圖。顯然強連通分量的定義已經沒有意義了，因為隻要存在a到b的路徑，那麼一定存在b到a的路徑。在無向圖裡面，有兩個定義：點雙連通分量和邊雙連通分量。

所謂點雙連通分量，就是指在a到b之間，存在兩條點不相交的路徑。而邊雙連通分量，就是指在a到b之間，存在兩條邊不相交的路徑。我們可以引申出割點和割邊（橋）的定義，即删掉某個點之後連通塊增加，那麼這個點就是割點；即連删掉某條邊之後，連通塊數目變多，那麼這個邊就是割邊或橋。

然後我們看這兩個東西在求法上要怎麼求。首先由于是無向圖，是以肯定不能走了一條邊然後走它的反向邊。對于點雙連通分量來說，由于是邊不能重複，是以我們直接在周遊邊的時候加一個判斷條件，如果這條邊通向剛剛來的點，也就是父親的時候，那麼直接跳過這條邊。對于邊雙連通分量，由于隻是要求邊不重複，是以點是可以重複走的，這裡用一個簡單的方法，就是統計走到剛剛來的點的次數，第一次的時候，由于可能是反向邊是以直接跳過，後面的話說明除了反向邊還有别的邊，是以可以走。這樣簡單的修改即可。

想了想還是把模闆都給出來吧。

inline void tarjan(int x,int fa)
{
        v[x]=1; sta.push(x);
  low[x]=dfn[x]=++dindex;
  for(int i=ls[x];~i;i=nxt[i])
  {
    int y=g[i];
    if (y==fa) continue;
    if (!dfn[y])
    {
      tarjan(y,x); low[x]=min(low[x],low[y]);
    } else if (v[y]) low[x]=min(low[x],dfn[y]);
  }
  if (dfn[x]==low[x])
  {
    cnt++; int j=0;
    do
    {
      j=sta.top();sta.pop();
      v[j]=0; belong[j]=cnt;
    } while (j!=x);
  }
}      

inline void tarjan(int x,int fa)
{
        int t=0;
        v[x]=1; sta.push(x);
  low[x]=dfn[x]=++dindex;
  for(int i=ls[x];~i;i=nxt[i])
  {
    int y=g[i];
    if (y==fa&&!t){t++;continue;}
    if (!dfn[y])
    {
      tarjan(y,x,root); low[x]=min(low[x],low[y]);
    } else if (v[y]) low[x]=min(low[x],dfn[y]);
  }
  if (dfn[x]==low[x])
  {
    cnt++; int j=0;
    do
    {
      j=sta.top();sta.pop();
      v[j]=0; belong[j]=cnt;
    } while (j!=x);
  }
}