POJ 1094 Sorting It All Out

POJ 1094 Sorting It All Out - (拓扑排序)

本文主要是介绍POJ 1094 Sorting It All Out - (拓扑排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=1094

拓扑排序
当然这份代码是没有AC的，因为 unodered_map 在 POJ 上不能通过编译。
我也不知道 C++ 11 之前 hash 应该用什么。。到时候换一下好了。
另外现在感觉代码比较规范，很可能会 TLE 。

(看了讨论区，发现只要在有环之前完成排序就可以，然后输出此时所用的关系数量，这题目也是迷)

#include <stdio.h>  
#include <vector>   
#include <algorithm>
#include <set>
#include <unordered_map>
#include <stack>
using namespace std;//POJ 1094 Sorting It All Outstruct node
{int ref;char character;vector<node*> next;node(char c) :character(c), next(0), ref(0) {}node() :character(0), next(0), ref(0) {}
};int main()
{char buffer[5];int n, m;while (~scanf("%d%d", &n, &m)){if (n == 0)break;//read the m lines of relationsset<char> nodes;unordered_map<char, node*> nodes_info;for (int i = 0; i < m; ++i){char a, b;scanf("%s", buffer); sscanf(buffer, "%c<%c", &a, &b);nodes.insert(a);nodes.insert(b);try { nodes_info.at(b); }catch (std::out_of_range& e) { nodes_info[b] = new node(b); }try { nodes_info.at(a); }catch (std::out_of_range& e) { nodes_info[a] = new node(a); }vector<node*>::iterator it = nodes_info[a]->next.begin();for (; it != nodes_info[a]->next.end(); ++it)if (*it == nodes_info[b])break;if (it == nodes_info[a]->next.end()){nodes_info[a]->next.push_back(nodes_info[b]);++nodes_info[b]->ref;}}//no possibility to form a relationif (n > m + 1){//check out whether there exists a circlestack<char> stk;int counter = 0;for (set<char>::iterator it = nodes.begin(); it != nodes.end(); ++it)if (nodes_info[*it]->ref == 0){stk.push(*it);counter++;}while (!stk.empty()){char c = stk.top(); stk.pop();for (vector<node*>::iterator it = nodes_info[c]->next.begin();it != nodes_info[c]->next.end(); ++it){if (--(*it)->ref == 0){stk.push((*it)->character);counter++;}}}if (nodes.size() > counter){printf("Inconsistency found after %d relations.\n", m);continue;}//no circle, so not determinedprintf("Sorted sequence cannot be determined.\n");continue;}//has possibility to form the relationelse{char* result = new char[n];int cur_pos = 0;stack<char> stk;int counter = 0;for (set<char>::iterator it = nodes.begin(); it != nodes.end(); ++it)if (nodes_info[*it]->ref == 0){stk.push(*it);counter++;}bool isDetermined = true;while (!stk.empty()){if (stk.size() > 1)isDetermined = false;char c = stk.top(); stk.pop();result[cur_pos++] = c;for (vector<node*>::iterator it = nodes_info[c]->next.begin();it != nodes_info[c]->next.end(); ++it){if (--((*it)->ref) == 0){stk.push((*it)->character);counter++;}}}if (nodes.size() > counter)printf("Inconsistency found after %d relations.\n", m);else if (!isDetermined)printf("Sorted sequence cannot be determined.\n");else {printf("Sorted sequence determined after %d relations: ", m);for (int i = 0; i < n; ++i)printf("%c", result[i]);printf(".\n");}delete[] result;}}system("pause");return 0;
}