2025年C 数据结构之拓扑排序：Leagal or Not

编程基础 • 2025-03-27 09:17 • 阅读 59

求一个有向无环图的拓扑排列：首先所有有入度的节点均不能排在第一个。选择一个入度为0的节点作为序列的第一个结点。当该节点被选为序列的第一个结点后，将该点从图中删去，同时删去以该结点为弧尾的所有边，得到一个新图。那么这个新图的拓扑序列即为原图的拓扑序列中除去第一个结点后剩余的序列。同样，在新图上选择一个入度为0的节点作为原图的第二个节点，并在新图中去以该结点为弧尾的所有边，得到一个新图，重复同样的方法，直到所有的结点和边都从原图中删去。若在所有节点尚未被完全删去时即出现了找不到入度为0的节点的情况，则说明剩余的节点形成一个环路，拓扑失败，原图无拓扑序列。我们使用队列来存储入度为0的节点。

1.Leagal or Not 。A是B的师傅，B是C师父，C是A师父，判读图是否为有向无环图

输入第一行M N，M人数，N表示关系数
3 2
0 1
1 2
2 2
0 1
1 0

输出 YES NO

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> edge[501];
queue<int> 	Q;
int main()
{
	int inDegree[501];//统计每个节点的入度 
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0) break;
		for(int i=0;i<n;i++)
		{
			inDegree[i]=0;
			edge[i].clear();
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);//由a指向b的边 
			inDegree[b]++;//累加b 的入度 
			edge[a].push_back(b);//把b加入a的邻接表 
		}
		while(Q.empty()==false) 	Q.pop();//清空上一组数据留下的数据 
		for(int i=0;i<n;i++)
		{
			if(inDegree[i]==0) Q.push(i);//入度为0的边入队 
		}
		int cnt=0;
		while(Q.empty()==false)//当入度为0的边未被取完的时候，重复 
		{
		int nowP=Q.front();//取出对头节点编号，本例不需要求出确定的拓扑排序，不做处理，否则将节点紧接着放在已经确定的拓扑序列之后 
		    Q.pop();
			cnt++;//弹出对头元素，确定节点个数加一 
			for(int i=0;i<edge[nowP].size();i++)
			{//将节点以及以其为弧尾的所有边去除 
				inDegree[edge[nowP][i]]--;//边所指后继节点入度-1 
				if(inDegree[edge[nowP][i]]==0)
				{//若该节点入度为0，将其放入队列中 
					Q.push(edge[nowP][i]);
				}
			} 
		}
		if(cnt==n) puts("YES");
		else puts("NO");
	}
	return 0;
}

2025年C 数据结构之拓扑排序：Leagal or Not

相关推荐