首页 > 代码库 > 拓扑排序
拓扑排序
之前很傻,,感觉看不到拓扑是啥东西。。脑子太烂了吧。。。今晚上瞄了一眼就懂了。。
我就放代码上来就行了。。注释也不打了,,因为太简单了。
#include <iostream>#include <cstring>using namespace std;#define CC(i) memset(i, 0, sizeof(i))const int maxn=105;int g[maxn][maxn], n, m, vis[maxn], top[maxn], cnt;bool dfs(int u) { vis[u]=-1; for(int v=1; v<=n; ++v) if(g[u][v]) { if(vis[v]==-1) return false; else if(!vis[v] && !dfs(v)) return false; } vis[u]=1; top[cnt--]=u; return true;}bool toposort() { CC(vis); CC(top); cnt=n; for(int i=1; i<=n; ++i) if(!vis[i] && !dfs(i)) return false; return true;}int main() { int u, v; cin >> n >> m; for(int i=1; i<=m; ++i) { cin >> u >> v; g[u][v]=1; } if(toposort()) { cout << "Yes\n"; int i; for(i=1; i<n; ++i) cout << top[i] << " < "; cout << top[i] << endl; } else cout << "No\n"; return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。