首页 > 代码库 > poj 1094 Sorting It All Out
poj 1094 Sorting It All Out
题目链接：http://poj.org/problem?id=1094
分析：
此题目涉及到图论拓扑排序的多个知识点：
1.判断给定的图是否可以拓扑排序；
2.判断给定的图能否产生一个唯一的拓扑排序，即全序；
代码如下：
#include <iostream>#include <fstream>#include <queue>using namespace std;const int MAX_N = 30;int graph[MAX_N][MAX_N];int set[MAX_N];int topoSort[MAX_N];int symbolNum;int result;void TopologicalSorting(int vertexNum, int j, int inDegree[]){ queue<int> Q; int count = 0; int flag = 0; for (int i = 0; i < vertexNum; ++ i) { if (set[i] == 1 && inDegree[i] == 0) Q.push(i); } if (flag == 0 && Q.size() >= 2) flag = 1; while (!Q.empty()) { int num = 0; int vertex; vertex = Q.front(); Q.pop(); topoSort[count] = vertex; for (int i = 0; i < vertexNum; ++i) { if (graph[vertex][i] != 0 && --inDegree[i] == 0) { Q.push(i); ++num; } } ++count; if (flag == 0 && num >= 2) flag = 1; } if (count != symbolNum) result = 1; else if (count == vertexNum && j == 0 && flag == 1) result = 2; else if (count == vertexNum && flag == 0) result = 3;}int main(){ int i, j, relations; char a, b, tmp; int flagOutput = 0; int inDegree[MAX_N]; int inDegreeCopy[MAX_N]; while ((cin >> i >> j) && (i != 0) && (j != 0) ) { memset(graph, 0, sizeof(graph)); memset(inDegree, 0, sizeof(inDegree)); memset(set, 0, sizeof(set)); memset(topoSort, 0, sizeof(topoSort)); memset(inDegreeCopy, 0, sizeof(inDegreeCopy)); symbolNum = result = relations = flagOutput = 0; if (j < i-1) { flagOutput = 1; result = 2; cout << "Sorted sequence cannot be determined.\n"; } while(j--) { cin >> a >> tmp >> b; ++relations; /* 统计出现的元素个数 */ if (set[a-‘A‘] != 1) set[a-‘A‘] = 1, ++symbolNum; if (set[b-‘A‘] != 1) set[b-‘A‘] = 1, ++symbolNum; ++inDegree[b - ‘A‘]; graph[a - ‘A‘][b - ‘A‘] = 1; if (flagOutput == 0) { for (int k = 0; k < i; ++k) inDegreeCopy[k] = inDegree[k]; TopologicalSorting(i, j, inDegreeCopy); } if (flagOutput == 0 && result == 1) { flagOutput = 1; cout << "Inconsistency found after " << relations << " relations.\n"; } if (flagOutput == 0 && symbolNum == i && result == 3) { char vertex; flagOutput = 1; cout << "Sorted sequence determined after " << relations << " relations: "; for (int j = 0; j < i; ++j) { vertex = topoSort[j] + ‘A‘; cout << vertex; } cout << ".\n"; } if (flagOutput == 0 && result == 2) { flagOutput = 1; cout << "Sorted sequence cannot be determined.\n"; } } if (flagOutput == 0 && symbolNum < i) { flagOutput = 1; cout << "Sorted sequence cannot be determined.\n"; } } return 0;}
poj 1094 Sorting It All Out
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。