本文主要是介绍zoj 1060 poj 1094 Sorting It All Out，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：将给定的关系按从小到大排成一个唯一的序列。
思路：没输入一条边，使用拓扑排序判断能否得到最终结果，拓扑排序的结果有三种情形。
⑴如果该图存在环，那么给定的关系肯定互相矛盾。
⑵如果不存在环，但是拓扑排序结束后，排序得到的序列中的元素个数小于给定的元素个数，那么给定的关系不足以判断出全部元素的大小关系。
⑶如果拓扑出来的序列中的元素个数等于给定的元素个数，那么给出的关系可以判断出全部元素的大小 关系。
注意：此题要求所得序列唯一，若拓扑排序过程中栈中元素个数大于一个，则说明此时所得序列不唯一。
代码：
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>using namespace std;const int maxn = 30;int n,m;
vector<int> list[maxn]; //邻接表
bool vis[maxn]; //记录元素是否出现
int ind[maxn]; //入度
int cnt; //当前出现的点的数量
char res[maxn]; //结果 /*
** 返回序列的元素个数，-1代表有环
*/
int TopSort(){stack<int> st;int d[maxn];int f = 1;for(int i = 0; i < n; i++){d[i] = ind[i];if(d[i] == 0 && vis[i]) st.push(i);}for(int i = 0; i < cnt; i++){if(st.empty()) return -1;if(st.size() > 1) f = 0;int u = st.top(); st.pop(); res[i] = u + 'A';for(int j = 0; j < list[u].size(); j++){if(--d[list[u][j]] == 0) st.push(list[u][j]);}}res[cnt] = '\0';if(f) return cnt;else return 0;
}bool Input(){int flag = 0;//记录拓扑排序返回的状态 -1存在环 0<flag<n表示不能确定 int k = 0; //在第k条关系能确定结果 char u,v;cnt = 0; cin>>n>>m;if(n == 0 && m == 0)return false;for(int i = 0; i < n; i++) {list[i].clear();ind[i] = 0;vis[i] = false;}for(int i = 0; i < m; i++){cin>>u;getchar();cin>>v;list[u-'A'].push_back(v-'A');ind[v-'A']++;if(!vis[u-'A']) {vis[u-'A'] = true; cnt++;}if(!vis[v-'A']) {vis[v-'A'] = true; cnt++;}if(flag != -1 && flag != n) {flag = TopSort(); k = i;}}if(flag == -1){printf("Inconsistency found after %d relations.\n",k+1); }else if(flag < n){printf("Sorted sequence cannot be determined.\n");}else{printf("Sorted sequence determined after %d relations: %s.\n",k+1,res);}return true;
}int main(){//freopen("data.in","r",stdin);//freopen("data.out","w",stdout);while(Input());return 0;
}这篇关于zoj 1060 poj 1094 Sorting It All Out的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
