连通图（求连通分量）

连通图中的连通分量个数求法：
可以根据最早时间戳和辅助时间戳low[]和dfn[]

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 1005
int dfn[maxn],low[maxn],vis[maxn],insta[maxn],stac[maxn];
int bel[maxn];
int cnt,times,top;
int n,m;
int in[maxn],out[maxn];//入度和出度
vector<int>vec[maxn];
void init()//板子，求连通分量的板子
{

    times=cnt=top=0;
    memset(in,0,sizeof(in));//清空
    memset(out,0,sizeof(out));//清空
    memset(dfn,0,sizeof(dfn));//时间戳
    memset(vis,false,sizeof(vis));//判断是否搜索过
    memset(low,0,sizeof(low));
    memset(insta,false,sizeof(insta));//判断是否入栈
    memset(stac,0,sizeof(stac));
    memset(vec,0,sizeof(vec));

}
void dfs(int x)
{
    times++;
    dfn[x]=times;
    low[x]=times;
    vis[x]=true;
    insta[x]=true;
    stac[top]=x;
    top++;
    for(int i=0;i<vec[x].size();i++)
    {
        int v=vec[x][i];
        if(!vis[v])
        {
            dfs(v);
            low[x]=min(low[x],low[v]);
        }
        else
        {
            if(insta[v]==true)
            {
                low[x]=min(low[x],dfn[v]);
            }
        }
    }
    if(low[x]==dfn[x])//说明该点走过的是一个连通分量
    {
        cnt++;
        while(top>0&&stac[top]!=x)
        {
            top--;
            int u=stac[top];
            bel[u]=cnt;//缩点
            insta[u]=false;
        }
    }
}
void slove(int n)
{

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            dfs(i);
    }
    if(cnt==1)
    {
        printf("1\n0\n");
        return ;
    }
    for(int u=1;u<=n;u++)
    {
        for(int j=0;j<vec[u].size();j++)
        {
            //int v=vec[u][j];
            if(bel[u]!=bel[vec[u][j]])
            {
                out[bel[u]]++;
                in[bel[vec[u][j]]]++;
            }
        }
    }
    int ansx=0,ansy=0;
    for(int i=1;i<=cnt;i++)
    {
        if(in[i]==0)
            ansx++;
        if(out[i]==0)
            ansy++;
    }
     printf("%d\n%d\n",ansx,max(ansx,ansy));


}
int main()
{
int v;
   while(~scanf("%d",&n))
   {
       init();
       for(int i=1;i<=n;i++)
       {
           while(scanf("%d",&v)&&v)
           {
               vec[i].push_back(v);
           }
       }
       slove(n);

   }




}