图结构练习——判断给定图是否存在合法拓扑序列 Time Limit: 1000MS Memory Limit: 65536KB Problem Description
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
Input
输入包含多组，每组格式如下。 第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10) 后面m行每行两个整数a b，表示从a到b有一条有向边。
Output
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。
Example Input
1 0 2 2 1 2 2 1
Example Output
YES
代码：
#include<stdio.h> #include<string.h> int map[15][15]; int vis[15];/*标记入度*/ int flag; void tuopsort(int n) { int i, j, k; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { if(vis[j] == 0)//从小到大找，第一个入度为0的 { vis[j]--;//此时为-1，相当于删除的意思 k = j;//记录该城市编号 break; } } if(j == n+1)//如果满足代表没有找到，标记一下退出循环 { flag = 1; break; } for(j = 1; j <= n; j++) { if(map[k][j] == 1)//k->j如果存在道路，让其入度减1，因为之前变成-1，相当于没有了 { map[k][j] = 0;//因为k没有了，所以k->j的道路也就没有了 vis[j]--;//入度减1 } } } } int main() { int n, m, u, v; while(~scanf("%d %d", &n, &m)) { flag = 0; memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); while(m--) { scanf("%d %d", &u, &v); map[u][v] = 1;//标记该路连通u->v vis[v]++;//入度++ } tuopsort(n);//拓扑排序 if(!flag) { printf("YES\n"); } else printf("NO\n"); } return 0; }另外一种方法：前向星
#include<bits/stdc++.h> using namespace std; struct node { int to, next; }; node Map[1000]; int head[15]; int ru[15]; int q[15], n; void tp() { int cnt = 0, i; for(i = 1; i <= n; i++)//遍历一遍n找出(入度为0的点)入队列 { if(ru[i] == 0) q[cnt++] = i; } for(i = 0; i < cnt; i++)//遍历m条边 so 时间复杂度O(n + m) { int u = q[i]; for(int j = head[u]; ~j; j = Map[j].next) { int to = Map[j].to; ru[to]--;//入度-- if(!ru[to])//如果为0， 入队列 q[cnt++] = to; } } if(cnt == n) printf("YES\n"); else printf("NO\n"); } int main() { int m, u, v; while(~scanf("%d %d", &n, &m)) { memset(head, -1, sizeof(head)); memset(ru, 0, sizeof(ru)); int cnt = 0; while(m--) { scanf("%d %d", &u, &v); ru[v]++;//入度++ Map[cnt].to = v;//前向星建图 Map[cnt].next = head[u]; head[u] = cnt++; } tp(); } return 0; }