POJ2186(有向图缩点&判图连通)

#include"cstdio"
#include"cstring"
#include"vector"
using namespace std;
const int MAXN=10005;
int V,E;
vector<int> G[MAXN];
vector<int> rG[MAXN];
int vis[MAXN];
int deg[MAXN];
int pos;
void dfs(int u)
{
    vis[u]=1;
    pos=u;
    for(int i=0;i<G[u].size();i++)
    {
        int to=G[u][i];
        if(!vis[to])
        {
            dfs(to);
        }
    }
}
void rdfs(int u)
{
    vis[u]=1;
    for(int i=0;i<rG[u].size();i++)
    {
        int to=rG[u][i];
        if(!vis[to])
        {
            rdfs(to);
        }
    }
}
bool pass()
{
    memset(vis,0,sizeof(vis));
    dfs(1);
    memset(vis,0,sizeof(vis));
    rdfs(pos);
    for(int i=1;i<=V;i++)
        if(!vis[i])    return false;
    return true;
}
int index;
int dfn[MAXN],low[MAXN];
int stack[MAXN],top;
int cpnt[MAXN],cnt;
inline int min(int a,int b)
{
    return a > b? b: a;
}
void tarjan(int u,int fa)
{
    stack[top++]=u;
    dfn[u]=low[u]=++index;
    for(int i=0;i<G[u].size();i++)
    {
        int to=G[u][i];
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=min(low[u],low[to]);
        }
        else low[u]=min(low[u],dfn[to]);//注意有向图与无向图缩点的不同 
    }
    if(dfn[u]==low[u])
    {
        int v;
        ++cnt;
        do{
            v=stack[--top];
            cpnt[v]=cnt;
        }while(u!=v);
    }
}
int seek()
{
    for(int i=1;i<=V;i++)
        for(int j=0;j<G[i].size();j++)
        {
            int to=G[i][j];
            if(cpnt[i]!=cpnt[to])
            {
                deg[cpnt[i]]++;
            }
        }
    int v;
    int flag=0;
    for(int i=1;i<=cnt;i++)
        if(deg[i]==0)//答案肯定为叶子结点 
        {
            v=i;
            flag++;
        }
    if(flag>1)    return 0;//必须只存在一个叶子结点 
    int ans=0;
    for(int i=1;i<=V;i++)
        if(cpnt[i]==v)    ans++;
    return ans;
}
int main()
{
    while(scanf("%d%d",&V,&E)!=EOF)
    {
        for(int i=1;i<=V;i++)
        {
            G[i].clear();
            rG[i].clear();
        }
        for(int i=0;i<E;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            rG[v].push_back(u);
        }
        if(pass())
        {
            index=0;
            memset(dfn,0,sizeof(dfn));
            memset(low,0,sizeof(low));
            top=0;
            cnt=0;
            memset(cpnt,0,sizeof(cpnt));
            tarjan(1,-1);
            memset(deg,0,sizeof(deg));
            int ans=seek();
            printf("%d\n",ans);
        }
        else
        {
            printf("0\n");
        }
    }
    
    return 0;
}