题意：给定n个二元组（u，v)表示u
分析：dfs搜索，如果存在有向环，那么无解。
#include
#include
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"); // 题目没说无解输出什么，应该是保证有解吧}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
