学步园

题目链接:   poj 2186

题目大意:   给定有向图，满足X使得图中任意的顶点Y都存在Y-->X的路径

                  计算X满足条件的顶点总数

解题思路:  
Kosataju找联通分量，缩成点

                  出度为0的顶点必须有且仅有一个

                  如果出度为0的顶点有若干个，那么这些联通分量之间是不可到达的

                  出度为0的联通分量中的点都满足题意

代码:

//Final     Kosaraju+缩点
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 110000
struct snode{
	int to,next;
}edge1[MAX*50],edge2[MAX*50];
int n,Index1,Index2,visit[MAX],pre1[MAX],pre2[MAX],num[MAX];
int k,list[MAX],father[MAX],In[MAX],To[MAX];

void Add_edge(int a,int b)    //建立正向反向图
{
	edge1[Index1].to=b,edge1[Index1].next=pre1[a];
	pre1[a]=Index1++;
	edge2[Index2].to=a,edge2[Index2].next=pre2[b];
	pre2[b]=Index2++;
}

void Kosaraju(int u)          //Kosaraju搜索强联通分量
{
	int i,v;
	visit[u]=1;
	for(i=pre1[u];i!=-1;i=edge1[i].next)
	{
		v=edge1[i].to;
		if(!visit[v])
			Kosaraju(v);
	}
	list[k++]=u;
}

void DFS(int u,int Father)    //
{
	int i,v;
	visit[u]=2;
	father[u]=Father;
	for(i=pre2[u];i!=-1;i=edge2[i].next)
	{
		v=edge2[i].to;
		if(visit[v]==1)
			DFS(v,Father);
	}
}

void Add_edge2(int a,int b)   //建立缩点之后的图
{
	int i;
	if(a==b)
		return ;
	for(i=pre2[a];i!=-1;i=edge2[i].next)
	{
		if(edge2[i].to==b)    //去除重复的边
			return ;
	}
	In[b]++; To[a]++;
	edge2[Index2].to=b,edge2[Index2].next=pre2[a];
	pre2[a]=Index2++;
}

int main()
{
	int m,i,j,a,b,c,k1,k2,k3;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		Index1=Index2=0;
		memset(In,0,sizeof(In));
		memset(To,0,sizeof(To));
		memset(num,0,sizeof(num));
		memset(pre1,-1,sizeof(pre1));
		memset(pre2,-1,sizeof(pre2));
		memset(visit,0,sizeof(visit));
		memset(father,0,sizeof(father));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			Add_edge(a,b);
		}
		if(m<n-1)       //如果不能构成图或者树
		{
			printf("0\n");
			continue;
		}
		for(i=1,k=0;i<=n;i++)
		{
			if(!visit[i])
			{
				
				Kosaraju(i);

			}
		}	
		for(j=k-1,c=0;j>=0;j--)   //按照Kosaraju搜索点的顺序分块搜索
		{
			if(visit[list[j]]==1)
			   	DFS(list[j],++c);
		}
		Index2=0;             //初始化
		memset(pre2,-1,sizeof(pre2));
		for(i=1;i<=n;i++)     //为正向图建立缩点之后的图
		{
			for(j=pre1[i];j!=-1;j=edge1[j].next)
			{
				Add_edge2(father[i],father[edge1[j].to]);
			}
		}
		if(c==1)              //为联通图则输出n
		{
			printf("%d\n",n);
			continue;
		}
		for(i=1;i<=n;i++)
			num[father[i]]++;
		for(i=1,a=-1,k1=k2=k3=0;i<=c;i++)
		{
			if(To[i]==0)      //终点
			{
				k2++;
				a=i;
			}
		}
		if(k2==1)             //***只有一个终点
			printf("%d\n",num[a]);
		else
			printf("0\n");
	}
	return 0;
}