轉(zhuǎn)載：https://blog.csdn.net/u013487630/article/details/19034877

https://blog.csdn.net/hongbudao/article/details/76798192

題目鏈接：http://bailian.openjudge.cn/practice/4084/

1、DFS

#include<stdio.h> #include<string.h> const int MAXN = 200; int n, m, G[MAXN][MAXN]; int c[MAXN];// 0 白色。 -1 灰色 1 黑色。 int topo[MAXN], t; bool dfs(int u) { c[u] = -1;//正在訪問。判回路。灰色。 for(int v = 1; 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 = 1; u <= n; u++) if(!c[u]) if(!dfs(u)) return false; return true; } int main() { while(scanf("%d%d", &n, &m)!=EOF) { memset(G, 0, sizeof(G)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); G[v][u] = 1; //<span style="font-family:'Lucida Grande', Verdana, 'Bitstream Vera Sans', Arial, sans-serif;">曾經(jīng)以為這是反向邊 廢了好長時間了解。。其實(shí)這樣才是正向邊。= - 表示 v>u有一條路。</span> } toposort(); for(int i = n; i >=1; i--) printf(i==n?"v%d":" v%d", topo[i]); printf("\n"); } return 0; }

2、基于入度

#include<cstdio> #include<vector> using namespace std; vector<int> g[105]; bool vis[105]; int in[105],v,a,from,to; int main(){ scanf("%d%d",&v,&a); while(a--){ scanf("%d%d",&from,&to); g[from].push_back(to); in[to]++; } int cnt = 0; while(cnt < v){ for(int i =1;i<=v;i++){ if(in[i]==0&&!vis[i]){ printf("v%d ",i); vis[i] = 1; cnt++; for(size_t j=0;j<g[i].size();j++){ in[g[i][j]]--; } break; } } } printf("\n"); return 0; }

總結(jié)

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

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