sdut原題鏈接
圖結構練習——判斷給定圖是否存在合法拓撲序列 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 NO
Hint
Author 趙利強
以下為accepted代碼
#include <stdio.h>#include <string.h>int op, tp, n, m;int link[14], map[14][14], indegree[14];//拓撲排序算法核心語句void topo(){ for(int i = 1; i <= n; i++)//尋找入度為零的點 { if(indegree[i] == 0)//判斷是否是入度為零的點 link[tp++] = i;//將入度為零的點入隊 } while(op < tp)//更新的過程 { for(int i = 1; i <= n; i++)//尋找入度為當前隊列結點的點的點 { if(map[link[op]][i] == 1)//判斷是否入度為當前隊列結點 { indegree[i]--;//結點入度數目更新 if(indegree[i] == 0)//判斷更新后是否有入度為零的點 link[tp++] = i;//將更新后入度為零的點入隊 } } op++;//當前隊列結點出隊 } if(op == n)//判斷出隊結點數是否是總結點數，若是，則為合法拓撲序列，若不是，則存在有向回路 printf("YES/n"); else printf("NO/n");}int main(){ int u, v; while(scanf("%d %d", &n, &m) != EOF) { op = tp = 0;//隊列標記變量初始化 memset(map, 0, sizeof(map));//map數組初始化 memset(indegree, 0, sizeof(indegree));//indegree數組（記錄結點入度數目）初始化 for(int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); map[u][v] = 1; indegree[v] += 1; } topo(); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 108KBSubmit time: 2017-02-20 09:37:18****************************************************/新聞熱點
疑難解答
