您的当前位置:首页正文

拓扑排序判断有向图是否存在环

2023-02-20 来源:爱站旅游
导读拓扑排序判断有向图是否存在环
vector<int>v[MAX_N];
int n,m,sum[MAX_N];
bool topo(){
	int num=0;
	queue<int>q;
	//queue<int,vector<int>,greater<int> >q;
	for(int i=0;i<n;i++){
		if(sum[i]==0)
		q.push(i);
	}
	while(!q.empty()){
		int from=q.front();
		//printf("%d",&from);
		q.pop();
		for(int i=0;i<v[from].size();i++){
			int to=v[from][i];
			sum[to]--;
			if(sum[to]==0)
			q.push(to);
		}
		v[i].clear();
		num++;
	}
	if(num==n)
	return true;//无环 
	else
	return false;
}

因篇幅问题不能全部显示,请点此查看更多更全内容