数据结构实验之图论十：判断给定图是否存在合法拓扑序列

阳光穿透心脏的1/2处 2022-12-24 00:46 111阅读 0赞

## 数据结构实验之图论十：判断给定图是否存在合法拓扑序列 ##

Description  
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input  
输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

Output  
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

Sample  
Input  
1 0  
2 2  
1 2  
2 1  
Output  
YES  
NO

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int map[1100][1100], vis[1100], to[1100];//map记边，vis记录结点访问情况，to记录一个结点的入度数
    int main()
    {
        
    	int n,m,a,b,i,j;
    	while (~scanf("%d %d", &n, &m))
    	{
        
    		memset(map, 0, sizeof(map));
    		memset(vis, 0, sizeof(vis));
    		memset(to, 0, sizeof(to));
    		for (i = 0; i < m; i++)
    		{
        
    			scanf("%d %d", &a, &b);
    			map[a][b] = 1;
    			to[b]++;
    		}
    		int sum_point = n;//如果所有可输出，则sum_point为0
    		for (i = 1; i <= n; i++)
    		{
        
    			if (vis[i] == 0 && to[i] == 0)//结点未访问且该结点的入度为0
    			{
        
    				vis[i] = 1;//该点标记为已访问
    				sum_point--;//结点总数减一
    				for (int k = 1; k <= n; k++)//找到i与k之间有连线且ik线为k的入度，删除，并将k的入度减一
    				{
        
    					if (map[i][k] == 1)
    					{
        
    						map[i][k] = 0;
    						to[k]--;
    					}
    				}
    				i = 1;//找一个符合条件的i点，进行上述操作后，在从头开始寻找符合条件的新i点
    			}
    		}
    		if (sum_point)
    			printf("NO\n");
    		else
    			printf("YES\n");
    	}
    }

[拓扑排序原理简易图][Link 1]

[Link 1]: https://blog.csdn.net/qq_41713256/article/details/80805338?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160631457619724847155436%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160631457619724847155436&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-80805338.pc_first_rank_v2_rank_v28&utm_term=%E6%8B%93%E6%89%91%E5%BA%8F%E5%88%97&spm=1018.2118.3001.4449