判断有向图是否有环.txt

ACM资料大集合

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define NMAX 105
int path[NMAX][NMAX];
int Ingree[NMAX];//各个点的入度

//判断一个有向图是否有环
/*
输入：
4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

5
0 1 0 0 0
0 0 1 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0

4
0 1 0 0
0 0 1 1
0 0 0 1
0 0 0 0
输出：
yes
no
yes
no
*/
void getIn(int num)
{	//计算各个点的入度
	int j,sum,i;
	for(i=1;i<=num;i++)
	{
		sum=0;
		for(j=1;j<=num;j++)
			if(path[j][i]==1) sum++;
		Ingree[i]=sum;
	}
}

int cal(int num)
{	//使用拓扑排序的方法判断是否有环
	int i,k,now,count=0;
	int stack[NMAX];
	k=0;
	getIn(num);
	for(i=1;i<=num;i++)
		if(Ingree[i]==0) stack[k++]=i;//入度为0的点入栈
	while(k!=0)//栈不为空
	{	
		now=stack[--k];//将栈里元素A出栈
		count++;//符合拓扑序列的元素个数加1
		for(i=1;i<=num;i++)
		{
			if(path[now][i]==1) 
			{
				Ingree[i]--;//A元素指向的所有的点入度减1
				if(Ingree[i]==0) stack[k++]=i;//如果入度为0，再入栈
			}
		}
	}
	if(count<num) return 1;//不是所有的点符合拓扑序列，说明存在环
	else return 0;
}
int main()
{
	int num,i,j;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
		{
			for(j=1;j<=num;j++)
			scanf("%d",&path[i][j]);
		}
		if(cal(num)==1) cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	return 0;
}