//字典序號(hào)最小 #include <cstdio> #include <cstring> #define MAXN 517 int G[MAXN][MAXN]; //路徑 int in_degree[MAXN]; //入度 int ans[MAXN]; int n, m, x, y; int i, j;bool toposort() {for (i = 1; i <= n; i++) //從最小的開(kāi)始尋找，{ //這樣保證了有多個(gè)答案時(shí)序號(hào)小的先輸出int k = 1;while (in_degree[k] != 0&&k<=n) //尋找入度為零的點(diǎn)k++;if(k==n+1) return 0;ans[i] = k;in_degree[k] = -1;//更新為-1，后邊檢測(cè)不受影響，相當(dāng)于刪除節(jié)點(diǎn)for (int j = 1; j <= n; j++){if (G[k][j])in_degree[j]--; //相關(guān)聯(lián)的入度減1}}return 1; }void init() {memset(in_degree, 0, sizeof(in_degree));memset(ans, 0, sizeof(ans));memset(G, 0, sizeof(G)); }int main() {while (~scanf("%d%d", &n, &m)){init();for (i = 0; i < m; i++){scanf("%d%d", &x, &y);if(G[x][y]==0) in_degree[y]++;G[x][y] = 1;}toposort();for (i = 1; i < n; i++)printf("%d ", ans[i]);printf("%d\n", ans[n]);}return 0; } //字典序最小2 #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=500+10; int n,m; vector<int> G[maxn]; int in[maxn]; void topo() {priority_queue<int,vector<int>,greater<int> > Q; //保證小值int先出隊(duì)列int ans[maxn],cnt=0;for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);while(!Q.empty()){int u=Q.top(); Q.pop();ans[cnt++]=u;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(--in[v]==0)Q.push(v);}}printf("%d",ans[0]);for(int i=1;i<n;i++)printf(" %d",ans[i]);puts(""); } int main() {while(scanf("%d%d",&n,&m)==2){memset(in,0,sizeof(in));for(int i=1;i<=n;i++) G[i].clear();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);in[v]++;}topo();}return 0; } //一般的拓?fù)渑判?/span> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=500+10; int n,m; vector<int> G[maxn]; int in[maxn]; void topo() {priority_queue<int,vector<int>,greater<int> > Q; //保證小值int先出隊(duì)列int ans[maxn],cnt=0;for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);while(!Q.empty()){int u=Q.top(); Q.pop();ans[cnt++]=u;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(--in[v]==0)Q.push(v);}}printf("%d",ans[0]);for(int i=1;i<n;i++)printf(" %d",ans[i]);puts(""); } int main() {while(scanf("%d%d",&n,&m)==2){memset(in,0,sizeof(in));for(int i=1;i<=n;i++) G[i].clear();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);in[v]++;}topo();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的图论--拓扑排序--模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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