判断图中是否有环_c语言如何判断图是否有环

 来自：判断图中是否有环的三种方法_J先生的编程笔记的博客-CSDN博客_判断图中是否有环

有向图，自己的代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int e[100010],h[1000010],ne[1000010],idx;
int rd[100010];
int n, m;
int sum = 0;
bool st[1000010];
void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;
}
bool topsort()
{
	
	queue<int> q;
	for(int i = 1;i <= n;i ++ )
	{
		if(!st[i])
		{
			if(rd[i] == 0)
			{
			   q.push(i);
			   sum = sum + 1;
			   st[i] = true;
		    }
		}
	}
	
	while(!q.empty())
	{
		int t = q.front();
		for(int i = h[t]; ~ i ;i = ne[i])
		{
			int j = e[i];
			if(st[j] == true) continue;
			rd[j] = rd[j] - 1;
			if(rd[j] == 0)
			{
			   q.push(j);
			   st[j] = true;
			   sum = sum + 1; 
		    }
		}
		
		q.pop();
	}
	
	if(sum == n) return false;
	else return true;
}
int main()
{
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	while(m -- )
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		rd[y] = rd[y] + 1;
	}
	
	if(topsort())
	   cout << "Yes" << endl;
	else
	   cout << "No" << endl;
	   
	   return 0;
}