学步园

学习了一下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;
}