https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246

C++版本一

題解：拓撲排序

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans[N],cnt,flag,temp,sum; int in[N]; int mp[N][N]; char str; struct node{}; void dfs(){queue<int>q;for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);while(!q.empty()){int tmp=q.front();q.pop();ans[++cnt]=tmp;for(int i=1;i<=n;i++){if(mp[tmp][i]){in[i]--;if(in[i]==0){q.push(i);}}}} } void init(){memset(in,0,sizeof(in));memset(mp,0,sizeof(mp));cnt=0; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d%d",&n,&m)&&(m+n)){init();for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);mp[u][v]=1;in[v]++;}dfs();for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

DFS

#include <iostream> #include <cstdio> #include <queue> #include <map> #include <algorithm> #include <cstring> using namespace std; ///拓撲排序學習題 遞歸形式dfs 選中一個未排序的元素進行dfs把在他之后的裝進ans（倒著裝）并標記。int n,m,a,b,ans[101],mp[101][101]={0},vis[101]={0},k; bool dfs(int last) {vis[last]=-1;for(int i=1;i<=n;i++)if(mp[last][i]){if(vis[i]==0)dfs(i);else if(vis[i]==-1)return false;//形成了回路 無法繼續排序 -1表示i比last先入棧。}ans[--k]=last;vis[last]=1;return true; } int main() {while(scanf("%d%d",&n,&m)){if(!(n+m))break;k=n;memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));for(int i=0;i<m;i++){scanf("%d%d",&a,&b);mp[a][b]=1;}for(int i=1;i<=n;i++){if(!vis[i]){if(!dfs(i))break;}}for(int i=k;i<n;i++)printf("%d ",ans[i]);putchar('\n');} }

C++版本三

#include <cstdio> #include <cstring> const int maxn = 101;int g[maxn][maxn], id[maxn], q[maxn];int main() { // freopen("in", "r", stdin);int n, m, a, b, tmp;int front, tail;while (scanf("%d%d", &n, &m)) {if (n == 0 && m == 0)break;memset(g, 0, sizeof(g));memset(id, 0, sizeof(id));front = tail = 0;for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);g[a][b] = 1;id[b]++;}for (int i = 1; i <= n; i++)if (id[i] == 0)q[tail++] = i;while (tail != front) {tmp = q[front++];if (front == 1)printf("%d", tmp);elseprintf(" %d", tmp);for (int i = 1; i <= n; i++)if (g[tmp][i] != 0)if (--id[i] == 0)q[tail++] = i;}//whileprintf("\n");}//while return 0; }

C++版本四

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans[N],cnt,flag,temp,sum; int vis[N]; int mp[N][N]; char str; struct node{}; void dfs(int u){vis[u]=-1;for(int i=1;i<=n;i++){if(mp[u][i]){if(vis[i]==0)dfs(i);else if(vis[i]==-1)return;}}ans[cnt--]=u;vis[u]=1; } void init(){memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));cnt=n; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d%d",&n,&m)&&(m+n)){init();for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);mp[u][v]=1;}for(int i=1;i<=n;i++){if(!vis[i]){dfs(i);}}for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Ordering Tasks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。