poj1236+la4287[tarjan算法]

學習了一下tarjan求有向圖強連通分量算法。 最後果斷發現LRJ的白書就是。。。 然後發現百度百科上面那個tarjan算法圖講解還是不錯的吧。  個人感覺理解度 80%應該有了。 深受各種大牛不看題解，不用模板啟發，看懂思路代碼必須自己敲一下。   這個算法挺好。    順便學會了有向圖強連通縮點後求入度出度。 兩題就是一樣， 靠入度出度來解決最後的問題。 深感各種題都的會DP，自己還是都得接觸，一點不接觸DP全靠隊友本來就是不科學的做法。。。                                                                                                         ------By Besyes~【寫題解只為自己復習方便，不為別的。】  

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <algorithm>  
using namespace std;  
  
const int maxn=10000;  
  
int pre[maxn],sccno[maxn],low[maxn];  
int in[maxn],out[maxn];  
vector<int> G[maxn];  
int scc_cnt,dfs_clock;  
stack<int>s;  
  
void dfs(int u)  
{  
   pre[u]=low[u]=++dfs_clock;  
   s.push(u);  
   for(int i=0;i<G[u].size();i++)  
   {  
       int v=G[u][i];  
       if(!pre[v])  
       {  
           dfs(v);  
           low[u]=min(low[u],low[v]);  
       }  
       else if(!sccno[v])  
       low[u]=min(low[u],pre[v]);  
   }  
  
   if(low[u]==pre[u])  
   {  
       while(s.top()!=u)  
       {  
           sccno[s.top()]=scc_cnt;  
           s.pop();  
       }  
       sccno[u]=scc_cnt;  
       s.pop();  
       scc_cnt++;  
   }  
}  
  
void find_scc(int n)  
{  
    memset(sccno,0,sizeof(sccno));  
    memset(low,0,sizeof(low));  
    memset(pre,0,sizeof(pre));  
    scc_cnt=1; dfs_clock=0;  
    for(int i=0;i<n;i++)  
    {  
        if(!pre[i]) dfs(i);  
    }  
}  
  
int main()  
{  
    int n,a,b;  
    while(scanf("%d",&n)!=EOF)  
    {  
        int a;  
        for(int i=0;i<n;i++)  
        {  
            for(;;)  
            {  
                scanf("%d",&a);  
                if(!a) break;  
                else G[i].push_back(a-1);  
            }  
        }  
  
        find_scc(n);  
  
        //for(int i=0;i<n;i++)  printf("~%d ",sccno[i]);  
  
        for(int i=1;i<scc_cnt;i++) in[i]=1,out[i]=1;  
  
        for(int i=0;i<n;i++)  
            for(int j=0;j<G[i].size();j++)  
            {  
                int v=G[i][j];  
                if(sccno[i]!=sccno[v])  
                {  
                    in[sccno[v]]=0; out[sccno[i]]=0;  
                }  
            }  
  
        a=0;b=0;  
        for(int i=1;i<scc_cnt;i++)  
        {  
            if(in[i]!=0) a++;  
            if(out[i]!=0) b++;  
        }  
        printf("%d\n",a);  
        if(scc_cnt==2) printf("0\n");  
        else {int ans=max(a,b); printf("%d\n",ans);}  
  
    }  
    return 0;  
}