本文主要是介绍Sorting It All Out POJ（拓扑排序+floyd），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一个就是简单的拓扑排序，一个就是利用floyd判断是否存在环
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define MAXD 30
#define MAX_SIZE 1000
vector<int>G[MAXD];
int n,m;
char L[MAXD];
int du[MAXD];
int maps[MAXD][MAXD];
int Floyd(){for(int k = 0; k < n; k++)for(int i = 0; i < n ; i++)for(int j = 0; j < n; j++)if(maps[i][k] && maps[k][j])maps[i][j] = 1;for(int i = 0; i < n ; i++)if(maps[i][i]) return 0;return 1;
}
int toposort(){memset(du,0,sizeof(du));for(int i = 0; i < n ; i++)for(int j = 0; j < G[i].size(); j++){du[G[i][j]] ++;//printf("%d %d\n",i,j);}queue<int>q;int cnt = 0;for(int i = 0;i < n ;i++)if(!du[i]) q.push(i);while(!q.empty()){if(q.size() > 1) return 0;int t = q.front(); q.pop();L[cnt ++] = t + 'A';//printf("%c\n",t + 'A');for(int i = 0 ; i < G[t].size(); i++){int x = G[t][i];du[x]--;if(!du[x])q.push(x);}}if(cnt == n) return 1;else return -1;
}
int main(){while(scanf("%d%d",&n,&m)){if(!n && !m) break;for(int i = 0; i < n ; i++)G[i].clear();int i;memset(maps,0,sizeof(maps));char a[MAX_SIZE],b[MAX_SIZE],c[MAX_SIZE];for(int i = 0; i < m ; i++){getchar();scanf("%c%c%c",&a[i],&b[i],&c[i]);}for(i = 0; i < m ; i++){char x,y,z;int flag;x = a[i]; y = c[i]; z = b[i];maps[x - 'A'][y - 'A'] = 1;flag = Floyd();if(flag == 0){printf("Inconsistency found after %d relations.\n",i + 1);break;}if(z == '<')G[x - 'A'].push_back(y - 'A');elseG[y - 'A'].push_back(x - 'A');if(toposort() == 1){L[n] = '\0';printf("Sorted sequence determined after %d relations: %s.\n",i + 1,L);break;}else if(toposort() == -1){printf("Inconsistency found after %d relations.\n",i + 1);break;}}if(i == m)printf("Sorted sequence cannot be determined.\n");}return 0;
}
这篇关于Sorting It All Out POJ（拓扑排序+floyd）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
