題意：給定n個二元組（u，v)表示u<v。將這些元素排序。

分析：dfs搜索，如果存在有向環(huán)，那么無解。

#include<cstdio> #include<cstring> const int maxn = 1000; int n, m, G[maxn][maxn], c[maxn], topo[maxn], t; bool dfs(int u){c[u] = -1;for(int v = 0; v < n; v++) if(G[u][v]) {if(c[v]<0) return false;else if(!c[v]) dfs(v);}c[u] = 1; topo[--t]=u;return true; } bool toposort(){t = n;memset(c, 0, sizeof(c));for(int u = 0; u < n; u++) if(!c[u])if(!dfs(u)) return false;return true; } int main() {while(scanf("%d%d", &n, &m) == 2 && n) {memset(G, 0, sizeof(G));for(int i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v); u--; v--;G[u][v] = 1;}if(toposort()) {for(int i = 0; i < n-1; i++)printf("%d ", topo[i]+1);printf("%d\n", topo[n-1]+1);}elseprintf("No\n"); // 題目沒說無解輸出什么，應(yīng)該是保證有解吧} }

?

總結(jié)

以上是生活随笔為你收集整理的uva 10305拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。