Tarjan算法（求強連通分量與割點）

Tarjan算法，是以一位計算機界大佬的名字命名的算法，多用于解決LCA，割點，強連通分量等問題，下面是其發明者的簡短介紹。

Robert Tarjan，計算機科學家，以LCA、強連通分量等算法聞名。他擁有豐富的商業工作經驗，1985年開始任教于普林斯頓大學。

切入正題，我們先來看一下tarjan算法的第一個主要用途：求強連通分量。

1.強連通分量

什麼是強連通分量呢？

有向圖強連通分量：在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。 

通俗一點來說，就是假設有A,B,C三個點，他們之間存在一些線路，使得兩兩之間直接或間接連接配接，若在圖中屬于最多點間的強連通系統，那麼這樣的一個整體稱之為強連通分量。

我們來看一下這個算法的思路：

1. 定義三個必需的數組和一個必需的全局變量：作為“時間戳”的sequence[amount]數組，記錄目前點可以回溯到達的最靠向根節點的一個點的數組lowest_reach[amount],和記錄目前點是否在棧中的vis[amount]數組，以及記錄目前點的current_turn。如不用STL的話，還可以定義一個模拟棧stacks[amount]，和與之配套的指針top，最好由鄰接表（鍊式前向星）存儲圖。
2. 從給定的根節點出發，一個枝一個枝地搜尋這個資料樹，用vis[current_turn]=1标記在棧中的資料， 并以目前點為起點，沿着鄰接表已經記錄好的路線一直搜尋，若下一個點沒有被通路，則直接遞歸進行更深層的搜尋，不然直接将目前點的lowest_reach和這條路下一個點的lowest_reach取最小值。
3. 驅逐在棧中的且已被判定的強連通分量。

實作代碼：

int current_turn=0,top=0;
int secquence[360],stacks[360],lowest_reach[360];
bool vis[360];
///necessary preparation for tarjan
struct node
{
  int next,to
}nodes[360];
int heads[360];
void tarjan(int current)
{
   secquence[current]=lowest_reach[current]=++current_turn;
   stacks[top++]=current;
   vis[current]=1;
   for(int heads[current];i!=-1;i=nodes[i].next)
    {
         int toward=nodes[i].to;
         if(secquence[towrad]==0)
            {
                tarjan(toward);
                lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);
            }
         else 
             lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);
///the other opinion says it should be secquence[toward]
   if(secquence[current]==lowest_reach[current])
     {
         vis[current]=false;
         while(stacks[top--]!=current)
          {
               vis[stacks[top--]]=false; 
          } 
        top--;
     } 
           

 2.割點

  看一下割點的定義。

在一個無向圖中，如果有一個頂點集合，删除這個頂點集合以及這個集合中所有頂點相關聯的邊以後，圖的連通分量增多，就稱這個點集為割點集合。

如果某個割點集合隻含有一個頂點X（也即{X}是一個割點集合），那麼X稱為一個割點。

 連通分量指的是若幹點間各自互相有直接或者間接聯系的系統，這裡所說的“增多”可以說是把原圖一分為多。也就是說，割點就是，這個點的存在維系着兩側圖是否可以連通。

那麼我們如何求出這些割點呢？仍然是tarjan算法，但是和上邊相比有一些改動。

我們看一下改動後的思路：

1. 仍然是用sequence數組記錄通路次序，lowest_reach記錄可以回溯到的最靠近根節點的點，這裡的vis數組将直接标記割點，整個過程不需要棧，但需要一個根節點号，和一個用來記錄根節點子樹的變量child。
2. 按着鄰接表所存儲的路線向深處搜尋。當我們搜尋完下一個結點時，發現通路次序sequence小于等于下一個點的lowest_reach,若等于，則意味着下一個點至少不能回到目前點，也就是說不連通，标記目前點。同時若current_turn回到了根節點，那說明某個線路與根節點是連通的。此時child++,若根節點有兩棵及以上的子樹，則可以判定這個根節點也是割點。

實作代碼：

int current_turn=0,child=0;
int secquence[360],lowest_reach[360];
bool vis[360];
struct node
{
  int next,to
}nodes[360];
int heads[360];
void tarjan(int current,int root)
{
   secquence[current]=lowest_reach[current]=++current_turn;
   child=0;
   for(int heads[current];i!=-1;i=nodes[i].next)
    {
         int toward=nodes[i].to;
         if(secquence[towrad]==0)
            {
                tarjan(toward);
                lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);
                if(lowest_reach[current]>=sequence[current]&&current!=root
                        vis[current]=1;
                if(current==root)
                       child++;
            }
         else 
             lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);
     }
    if(child>=2&&current==root)
          vis[current]=1; 
 }