poj1236+la4287[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;  
}  

 

补充：软件开发 , C++ ,