POJ 1094 解题报告

本文主要是介绍POJ 1094 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题因为数据较小，有更简单的解法，比如闭包传递啥的（我也不懂）。我这里是用拓扑排序算的。

一个需要考虑的情况是：需要先检查是否有环。因为如果有环，也可能在检测到inconsistency之前就判断为can not determine了。

我的用时看了下是最久的，也不知为啥。

判断一个有向图是否有环：http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

thestoryofsnow

1094

Accepted

192K

766MS

C++

3374B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1094 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;enum Status
{INCONSIS, UNDETERM, SUCCESS
};bool isCyclic(int u, vector<bool> &visited, std::vector<bool> &instack, const vector<vector<int> > &outcomings)
{visited[u] = true;instack[u] = true;for (int i = 0; i < outcomings[u].size(); ++i){int v = outcomings[u][i];if (!visited[v]){if (isCyclic(v, visited, instack, outcomings)){return true;}}else if (instack[v]){return true;}}instack[u] = false;return false;
}Status toposort(const vector<pair<int, int> > &lessthans, int endindex, const int n, vector<int> &toposeq)
{vector<set<int> > incomings(n, set<int>());vector<vector<int> > outcomings(n, vector<int>());for (int i = 0; i < endindex; ++i){incomings[lessthans[i].first].insert(lessthans[i].second);outcomings[lessthans[i].second].push_back(lessthans[i].first);}vector<bool> visited(n, false), instack(n, false);for (int u = 0; u < n; ++u){if (!visited[u]){// there exists a circle, no one comes firstif(isCyclic(u, visited, instack, outcomings)){return INCONSIS;}}}stack<int> noincomings;for (int i = 0; i < n; ++i){if (incomings[i].size() == 0){noincomings.push(i);}}toposeq.clear();while (toposeq.size() < n){// there exists a circle, no one comes firstif (noincomings.size() < 1){// shouldn't happen, as I have checked if there is cycleassert (false);return INCONSIS;}// multiple nodes can come first, cannot determineif (noincomings.size() > 1){return UNDETERM;}int u = noincomings.top();noincomings.pop();toposeq.push_back(u);for (int i = 0; i < outcomings[u].size(); ++i){int v = outcomings[u][i];incomings[v].erase(u);if (incomings[v].size() == 0){noincomings.push(v);}}}return SUCCESS;
}int main()
{int n, m;while (scanf("%d%d", &n, &m) && !(!n && !m)){vector<pair<int, int> > lessthans;for (int i = 0; i < m; ++i){char A, B;scanf("\n%c<%c", &A, &B);// printf("[%c]<[%c]\n", A, B);lessthans.push_back(make_pair<int, int>(A - 'A', B - 'A'));}bool inconsis = false, success = false;int line = -1;vector<int> toposeq;;for (int i = 1; i <= m; ++i){Status status = toposort(lessthans, i, n, toposeq);if (status == INCONSIS){inconsis = true;line = i;break;}if (status == SUCCESS){line = i;success = true;break;}}if (inconsis){printf("Inconsistency found after %d relations.\n", line);}else if (success){printf("Sorted sequence determined after %d relations: ", line);for (int i = toposeq.size() - 1; i >= 0; --i){printf("%c", 'A' + toposeq[i]);}printf(".\n");}else{printf("Sorted sequence cannot be determined.\n");}}return 0;  
}

这篇关于POJ 1094 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---