学步园

题目链接:  poj
2762

题目大意: 给定有向图，问是否满足对于任意的顶点X和Y

                  使得X->Y或Y->X至少存在一条路径

解题思路:
联通分量找出，缩成点形成DAG(有向无环图)

                  使得缩点后的图满足题意，必须是单链图

                  换句话说同一个点只能有一个分支

                  有两个分支的话，分支之间是不能到达的

                  图1橙色顶点无法到达绿色还有另一橙色分支

                  而图2的绿色顶点都可以到达

                  判断单链图：缩点后有C块联通分量，则有1个入度0出度1，1个入度1出度 0，C-2个入度1出度1顶点

代码:

//Final    kosaraju+缩点+单链图
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1010
struct snode{
	int to,next;
}edge1[MAX*12],edge2[MAX*12],edge3[MAX*12];
int visit1[MAX],In[MAX],To[MAX],pre1[MAX],pre2[MAX],Index1,Index2,len,k,list[MAX];
int father[MAX],pre3[MAX],Index3;

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

void Add_edge2(int a,int b)  //建立逆向图
{
	edge2[Index2].to=b,edge2[Index2].next=pre2[a];
	pre2[a]=Index2++;
}

void Kosaraju(int u)     //第一次正向搜索
{
	int i,v;
	for(i=pre1[u];i!=-1;i=edge1[i].next)
	{
		v=edge1[i].to;
		if(visit1[v]==0)
		{
			visit1[v]=1;
			Kosaraju(v);
		}
	}
	list[k++]=u;
}

void DFS(int u,int Father)  //第二次是分块逆向搜索，搜索点的顺序与正向一样
{
	int i,v;
	visit1[u]=2;
	father[u]=Father;
	for(i=pre2[u];i!=-1;i=edge2[i].next)
	{
		v=edge2[i].to;
		if(visit1[v]==1)
			DFS(v,Father);
	}
}

void Add_edge3(int a,int b)   //建立缩点后的图
{
	int i;
	if(a==b)
		return ;
	for(i=pre3[a];i!=-1;i=edge3[i].next)   //如果有重边则不加入
	{
		if(edge3[i].to==b)
			return ;
	}
	In[b]++; To[a]++;
	edge3[Index3].to=b,edge3[Index3].next=pre3[a];
	pre3[a]=Index3++;
}

int main()
{
	int t,n,m,i,j,a,b,c,v,k1,k2,k3,pd;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		
		Index1=Index2=Index3=0;
		memset(In,0,sizeof(In));
		memset(To,0,sizeof(To));
		memset(pre1,-1,sizeof(pre1));  //正向图
		memset(pre2,-1,sizeof(pre2));  //逆向图
		memset(pre3,-1,sizeof(pre3));  //缩点后的图
		memset(visit1,0,sizeof(visit1));
		memset(father,0,sizeof(father));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			Add_edge1(a,b);
			Add_edge2(b,a);
		}
		if(m<n-1)     //边数小于顶点数-1不能构成图或者树
		{
			printf("No\n");
			continue;
		}
		for(i=1,k=0;i<=n;i++)
		{
			if(!visit1[i])
			{
				visit1[i]=1;
				Kosaraju(i);

			}
		}	
		for(j=k-1,c=0;j>=0;j--)
		{
			if(visit1[list[j]]==1)
			{
				DFS(list[j],++c);
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=pre1[i];j!=-1;j=edge1[j].next)
			{
				v=edge1[j].to;		
				Add_edge3(father[i],father[v]);
			}
		}
		if(c==1)
		{
			printf("Yes\n");
			continue;
		}
		for(i=1,k1=k2=k3=pd=0;i<=c;i++)  //缩点后的图是否为单链的树
		{
			if(In[i]==1&&To[i]==0)   //有一个终点
			{
				k1++;
				continue;
			}
			if(In[i]==0&&To[i]==1)   //有一个起点
			{
				k2++;
				continue;
			}
			if(In[i]==1&&To[i]==1)   //有c-2个中间点
			{
				k3++;
				continue;
			}
		}
		pd=k1+k2+k3;
		if(k1==1&&k2==1&&pd==c)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}