POJ 1094-Sorting It All Out

POJ 1094-Sorting It All Out Sorting It All Out Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 28397 Accepted: 9814 Description An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. Input Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. Output For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence. Sample Input 4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0 Sample Output Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined. Source East Central North America 2001


这一题有一定的难度,有很多细节需要兼顾。题目的意思为:给定一系列小于关系,问能否从中得出一个严格有序的序列。需要明确的是,题目所指的严格有序的序列需要满足如下几个条件:1.包含n个所有字母;2.每个字母都有明确的大小关系。 另外根据测试样例我们可以知道:每输入一个关系都要判断一次,如果可以得到严格有序序列,则输出结果,但这个测试用例后续的输入还是要输入的;如果出现相互依赖(环),也输出结果,同样的,这个测试用例后面的数据还是要输入;如果所有关系都输入了还不能得出一个严格有序的序列,则输入无法判断。 这一题很自然的想到用拓扑排序来做。下面我们先来回顾一下拓扑排序。 如上图是《算法导论》中关于拓扑排序的一个例子,这是某位教授起床后需要穿戴衣物的顺序,比如只有先穿了袜子才能穿鞋、但是穿鞋和戴手表并没有严格的先后顺序。拓扑排序的功能就是根据图(a)的拓扑图,得到图(b)中节点的先后顺序。 常见的拓扑排序算法有两种:Kahn算法和基于DFS的算法,这两种算法都很好理解,详细的解释请看维基百科Topological sorting,下面简要介绍一下这两个算法。 Kahn算法 拓扑排序强调先后顺序,先做的事情排在前面,那么反应到有向图上,最先做的事情就是没有入度的节点(可能 有/没有 出度)。所以Kahn算法很朴素,他就是把所有没有入度的点加入到集合S中,在S不为空的情况下循环:从S中取出一个节点a,把a加入到L链表的尾部,对于每一条a的出度边,如< a,b>,删除它,并把b的入度减一,如果b的入度也为0了,则又把b加入到集合S中。如果S为空了,但是图中还有边未删除,说明图中至少有一个,拓扑排序失败;否则拓扑排序成功,且链表L保存了一条拓扑排序链。(链表L的生成使用尾插法) 维基百科上关于Kahn算法的伪代码描述如下: [cpp] L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order) [/cpp] 基于DFS的算法 这个算法类似于深度优先搜索,它不断的递归访问下一个节点,直到不能再递归时,把最后一个节点插入到链表的头部,然后返回。 拿上面穿衣物的例子来说,如果我们首先选择了内裤,则可以递归访问裤子->腰带->夹克。到夹克时,无法递归了,则把夹克插入到L的头部,返回到腰带,腰带也无法递归了,则把腰带插入到L的头部,这个时候就形成了L:腰带->夹克的中间结果,也就是腰带要在夹克前面穿。这个算法不太好表述,还请大家看伪代码领会。(链表L的生成使用头插法) [cpp] L ← Empty list that will contain the sorted nodes while there are unmarked nodes do select an unmarked node n visit(n) function visit(node n) if n has a temporary mark then stop (not a DAG) if n is not marked (i.e. has not been visited yet) then mark n temporarily for each node m with an edge from n to m do visit(m) mark n permanently unmark n temporarily add n to head of L [/cpp] 那么问题来了,只使用拓扑排序并不能满足本题的要求。因为本题问的是能否生成一个严格有序的序列,一个拓扑序列并不一定是严格有序的序列,比如上图中的穿衣物生成的拓扑序列中,先穿袜子和先穿衬衫都是可以的,也就是说袜子和衬衫是没有明确的先后顺序的,所以这不是一个严格有序的序列。再比如下图的拓扑序列,也不是一个严格有序的序列,因为C和A,D,E,F无法比较大小。 那么怎么判断生产的拓扑序列是否是严格的有序序列呢?基本原则就是就是任意取序列中的两个点,看能不能比较大小,如果能则是严格有序,否则不是。 我起初想到的是对拓扑序列的第一个节点进行深度遍历,遍历之后如果所有的节点都访问了,那么这是一个严格有序的序列,否则不是。后来证明这是不正确的,比如上图从B点开始DFS,遍历完F之后回溯到B点再访问C点,这样即使它不是严格有序的,但DFS还是访问了所有节点。 后来想到了Floyd算法。对拓扑图进行Floyd算法之后,会得到任意两点之间的最短距离。如果拓扑序列中前面的节点都可以到达后面的节点(最短距离不为无穷),则是严格有序的;否则不是。比如上图的一个拓扑序列为BCADEF(不唯一,还可以是BADEFC),但是C到ADEF的最短距离都是无穷,所以这个序列不是严格有序的。 把这些大的问题搞清楚之后就可以写代码了,一些小细节可以看我代码里的注释。 [cpp] #include<iostream> //#include<set> #include<list> #include<string> #include<vector> using namespace std; int n,m; const int MAX_N=26; const int MAX_DIS=10000; //*******这些都是维基百科关于拓扑排序(DFS版)里的变量含义 int temporary[MAX_N]; int permanent[MAX_N]; int marked[MAX_N]; //******************************* int path[MAX_N][MAX_N]; //int dfs_visited[MAX_N]; list<int> L;//拓扑排序生产的顺序链 bool isDAG;//DAG=directed acyclic graph,无回路有向图 //每一个测试用例都要初始化路径 void init_path() { for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=0; } //每一次拓扑排序都要初始化temporary,permanent,marked void init_tpm() { isDAG=true; L.clear(); for(int i=0;i<n;i++) { temporary[i]=0; permanent[i]=0; marked[i]=0; } } //递归访问。具体看维基百科 void visit(int i) { if(temporary[i]==1) { isDAG=false; return; } else { if(marked[i]==0) { marked[i]=1; temporary[i]=1; for(int j=0;j<n;j++) { if(path[i][j]==1) { visit(j); } } permanent[i]=1; temporary[i]=0; L.push_front(i); } } } /* void init_dfs() { for(int i=0;i<n;i++) dfs_visited[i]=0; }*/ /* //DFS有缺陷 void DFS(int v) { if(dfs_visited[v]==0) { dfs_visited[v]=1; for(int i=0;i<n;i++) { if(dfs_visited[i]==0&&path[v][i]==1) { DFS(i); } } } }*/ //使用Floyd算法来判断生产的拓扑排序是否是严格有序的 bool Floyd() { int copy_path[MAX_N][MAX_N]; for(int i=0;i<n;i++)//首先复制一份路径图 for(int j=0;j<n;j++) { copy_path[i][j]=path[i][j]; if(i!=j&&copy_path[i][j]==0)//如果原来两点距离为0,说明他们是不直接连通的 copy_path[i][j]=MAX_DIS;//置为无穷 } //floyd算法 for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(copy_path[i][j]>copy_path[i][k]+copy_path[k][j]) copy_path[i][j]=copy_path[i][k]+copy_path[k][j]; vector<int> seq;//把原来用链表的拓扑序列转换成数组,方便后面的操作 list<int>::iterator it=L.begin(); while(it!=L.end()) { seq.push_back(*it); it++; } //如果这个拓扑链是严格有序的话,则前面的元素到后面的元素一定是可达的。 for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(copy_path[seq[i]][seq[j]]>=MAX_DIS)//如果不可达,则不是严格有序的。 return false; } } return true; } //拓扑排序DFS版本。返回0:有回路;1:虽然是拓扑排序,但非连通(不是严格有序);2:是拓扑排序且连通(严格有序)(即任意两个元素都可以比较大小) int topological_sorting() { for(int i=0;i<n;i++) { if(marked[i]==0) { visit(i); } } if(!isDAG) return 0; else { /*init_dfs(); DFS(*L.begin()); for(int i=0;i<n;i++) { if(dfs_visited[i]==0) { return 1; } }*/ if(Floyd()) return 2; else return 1; } } int main() { //freopen("input.txt","r",stdin); string tmp; while(cin>>n>>m&&n&&m) { init_path(); vector<string> relations(m); int i; for(i=0;i<m;i++)//一次性把所有输入都存起来,免得后续麻烦 { cin>>relations[i]; } int rs=-1; for(i=0;i<m;i++)//每增加一个关系,都要重新拓扑排序一次 { init_tpm();//每次都要初始化 tmp=relations[i]; path[tmp[0]-‘A’][tmp[2]-‘A’]=1; rs=topological_sorting(); if(rs==0) { cout<<"Inconsistency found after "<<i+1<<" relations."<<endl; break;//如果是回路的话,后续的输入可以跳过 } else if(rs==2)//成功 { cout<<"Sorted sequence determined after "<<i+1<<" relations: "; list<int>::iterator it=L.begin(); while(it!=L.end()) { char c=’A’+*it; cout<<c; it++; } cout<<"."<<endl; break;//后续输入跳过 } } if(i==m&&rs==1)//如果处理完所有输入都没有形成严格有序的拓扑序列 cout<<"Sorted sequence cannot be determined."<<endl; } return 0; } [/cpp] 我原本以为又是DFS,又是Floyd,算法时空效率会很低,但是提交后AC,用时125MS,内存244K,也不是很差。 代码中的拓扑排序算法使用的是基于DFS的版本,大家也可以改成Kahn算法。 如果觉得自己的代码是对的,但是提交WA的,可以使用这两个测试数据:数据1数据2]]>

1 thought on “POJ 1094-Sorting It All Out

  1. Pingback: LeetCode Course Schedule | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *