?

題目大意

?　　一個(gè)不同的值的升序排序數(shù)列指的是一個(gè)從左到右元素依次增大的序列。給你一系列形如A<B的關(guān)系，并要求你判斷是否能夠根據(jù)這些關(guān)系確定這個(gè)數(shù)列的順序（能，矛盾，不確定）。確定n個(gè)元素的順序后即可結(jié)束程序，可以不用考慮確定順序之后出現(xiàn)矛盾的情況。

?題解

　　如果A<B，則在圖中A結(jié)點(diǎn)向B結(jié)點(diǎn)連一條有向邊，這樣，如果出現(xiàn)了矛盾情況，則有向圖中出現(xiàn)了環(huán)。如果確定了數(shù)列的順序，則圖中存在一條鏈把1~n所有結(jié)點(diǎn)都串起來(lái)了。換句話說(shuō)，把這個(gè)有向圖的邊權(quán)都設(shè)為1，則該有向圖中的最長(zhǎng)路徑為n時(shí)，能夠確定序列順序。那么這道題就是拓?fù)渑判虻哪０孱}了。

#include <cstdio> #include <cstdarg> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <string> #include <iostream> using namespace std;#define NotVis 0 #define Finished 1 #define InStack -1const int MAX_NODE = 50;struct TopSort {int N;bool HaveCircle;int MaxDist;struct Node{int Color;//0:NotVis 1:Finished -1:InStackint Dist;vector<Node*> Next;}_nodes[MAX_NODE];stack<Node*> St;void Dfs(Node *cur){if (cur->Color == InStack){HaveCircle = true;return;}if (cur->Color == Finished)return;cur->Color = InStack;for (int i = 0; i < cur->Next.size(); i++){if (HaveCircle)return;Dfs(cur->Next[i]);}cur->Color = Finished;St.push(cur);}TopSort(int n):N(n){}void Build(int from, int to){_nodes[from].Next.push_back(_nodes + to);}void Init(){MaxDist = -1;while (!St.empty())St.pop();HaveCircle = false;for (int i = 1; i <= N; i++)_nodes[i].Color = _nodes[i].Dist = 0;}void GetMaxDist(){if (HaveCircle){MaxDist = -1;return;}stack<Node*> tempSt = St;while (!tempSt.empty()){Node *cur = tempSt.top();tempSt.pop();MaxDist = max(MaxDist, cur->Dist);for (int i = 0; i < cur->Next.size(); i++)cur->Next[i]->Dist = max(cur->Next[i]->Dist, cur->Dist + 1);}}void Proceed(){Init();for (int i = 1; i <= N; i++)Dfs(_nodes + i);GetMaxDist();} };int main() {int totNode, opCnt;string s;cin >> totNode >> opCnt;static TopSort g(totNode);for (int i = 1; i <= opCnt; i++){cin >> s;int a = s[0] - 'A' + 1, b = s[2] - 'A' + 1;if (s[1] == '>')swap(a, b);g.Build(a, b);g.Proceed();if (g.HaveCircle){printf("Inconsistency found after %d relations.\n", i);return 0;}else if (g.MaxDist == totNode - 1){printf("Sorted sequence determined after %d relations: ", i);stack<TopSort::Node*> temp = g.St;while (!temp.empty()){printf("%c", (int)(temp.top() - g._nodes) - 1 + 'A');temp.pop();}printf(".\n");return 0;}}printf("Sorted sequence cannot be determined.\n");return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/headboy2002/p/9180447.html

總結(jié)

以上是生活随笔為你收集整理的luogu1347 排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。