POJ - 2186 Tarjan的模闆題..

   暑假的時候研究過kosaraju~~A過一些強連通分量..Kosaraju需要做兩個圖, 一個原圖一個是原圖的反圖(每個邊的終點起點反過來..)..正着DFS一次...标記出棧順序..再根據這個出棧順序對反圖進行一次DFS..每次能周遊到的點就是在一起的強連通分量...

    Tarjan同樣是用的對圖DFS...Byvoid大牛的這個文章很适合初學者​​https://www.byvoid.com/blog/scc-tarjan​​

    隻說一些要注意的...

    1、Tarjan不是一次Tarjan(1)讓它搜就行了~~要循環所有的點...因為1不一定能到所有點..

    2、在DFS循環邊來判斷時...首先是看是不是以前通路過...如果不滿足再來看這個點是不是正在棧中..

    3、不一定在同一強連通分量的電Low值會相等...是以彈棧時的判斷條件不能是說Low相等就彈,而是說彈到一個Low = DFN 的點為止..

    4、彈棧時注意instack,也就是标記點是不是在棧中的要跟着更新... 

    5、可能有的點完全孤立..就是根本沒有邊...是以做完Tarjin後..檢查所有的點是不是都處理過了..如果有沒處理的...直接傳回沒有大牛( 0 )..

    這道題是要找所有人都能仰慕到的...也就是除了自己的所有強連通分量裡都能到自己的強連通分量就是一個大牛集合...這裡在做完Tarjan後...要先進行縮點..就是把每個強連通分量都縮成一個點..然後再來判斷...

Program::

//POJ2186 找大牛 Tarjin
#include<iostream>
#include<math.h>
#include<stack>
#define MAXN 15001
using namespace std;
struct pp
{
    int x,y,next;      
}line[MAXN*5],line2[MAXN*5];
int n,m,link[MAXN],tp[MAXN],low[MAXN],instack[MAXN],dfn[MAXN],p,numtp,sum[MAXN];
bool used[MAXN];
stack<int> mystack;
void trajin(int h)
{
   int i,k;  
   low[h]=dfn[h]=++p;  
   used[h]=instack[h]=true; 
   mystack.push(h);   
   k=link[h];
   while (k)
   {
       if (!used[line[k].y])
       {
          trajin(line[k].y);                  
          low[h]=min(low[h],low[line[k].y]);                 
       }else
       if (instack[line[k].y])
       {
          low[h]=min(low[h],dfn[line[k].y]);   //這裡用low[line[k].y]來更新結果同樣正确..但似乎會影響其他的找橋和割的運算
       }
       k=line[k].next;  
   }
   k=h; 
   if (low[k]==dfn[k])
   {           
       numtp++; 
       do
       {
           k=mystack.top();
           mystack.pop();
           instack[k]=true;
           tp[k]=numtp;                
       }while (low[k]!=dfn[k]); 
   }
   return;
}
void dfs(int h)
{
   int k;    
   used[h]=true;
   sum[h]++;
   k=link[h];
   while (k)
   {
      if (!used[line2[k].y]) dfs(line2[k].y);
      k=line2[k].next;   
   }
   return;
}
int getanswer()
{
   int i,ans,cow,k,p;  
   p=0; numtp=0;
   while (!mystack.empty()) mystack.pop();
   memset(used,false,sizeof(used));
   for (i=1;i<=n;i++) 
     if (!used[i]) 
     {
          memset(instack,false,sizeof(instack));
          trajin(i); 
     }
   k=0;
   memset(link,0,sizeof(link));
   for (i=1;i<=m;i++)
    if (tp[line[i].x]!=tp[line[i].y])
    {
        k++;
        line2[k].x=tp[line[i].x];
        line2[k].y=tp[line[i].y];
        line2[k].next=link[line2[k].x];
        link[line2[k].x]=k;                                 
    }
   for (i=1;i<=n;i++)
     if (!tp[i]) return 0;
   p=n;
   n=numtp;
   memset(sum,0,sizeof(sum));
   for (i=1;i<=n;i++)
   {
      memset(used,false,sizeof(used)); 
      dfs(i);
   }
   for (i=1;i<=n;i++) 
     if (sum[i]==n) cow=i;
   ans=0;
   for (i=1;i<=p;i++)
     if (tp[i]==cow) ans++;  
   return ans;
}
int main()
{  
   while (~scanf("%d%d",&n,&m))
   {
       memset(line,0,sizeof(line));
       memset(link,0,sizeof(link));
       memset(tp,0,sizeof(tp));
       int i;
       for (i=1;i<=m;i++) 
       {
           scanf("%d%d",&line[i].x,&line[i].y);
           line[i].next=link[line[i].x];
           link[line[i].x]=i; 
       } 
       printf("%d\n",getanswer());
   }   
   return 0;   
}