建网站程序下载,营销型网站更受用户欢迎的原因是,网络营销的概念可译为,陕西建设银行官网站这道题目考察了拓扑排序的基本思想#xff1a;每一步寻找一个入度为0的结点#xff0c;然后 删除之。将这个结点指向的结点入度减1。删除从这个结点出发的所有边
同时考察了对于一个有向图是否有环、是否严格有序的判断。#xff08;当发现多个结点的度 为0时#xff0c;则…这道题目考察了拓扑排序的基本思想每一步寻找一个入度为0的结点然后 删除之。将这个结点指向的结点入度减1。删除从这个结点出发的所有边
同时考察了对于一个有向图是否有环、是否严格有序的判断。当发现多个结点的度 为0时则不是严格有序。当发现没有结点入度为0时则有环 需要注意的是逻辑上的关系。“Sorted sequence cannot be determined.”这个判断 要放在最后即只有发现了所有的点都没有环且并没有发现严格有序性质的时候 才可以判为“Sorted sequence cannot be determined.逻辑上的判决一定要注意优先级。
这个问题中优先级最高的是判断有环。一旦发现找不到度为0的结点则立即return。
第二优先级是是否严格有序的判断。当每一步能且只能找到一个度为0的结点则return。
第三优先级是无法确定。(当发现无法确定时并不能立即return因为还需要判断是否有环
思维方式:当条件x成立时另外的条件yz是否一定不成立。如果一定不成立 则可以断言return。否则必须继续判断下去。 提交记录 1.样例未过由于拓扑排序算法中处理过程中入度减1的同时并没有将对应的边删掉。 2.样例未过 由于在子函数judge中对graph图进行了修改导致后面处理失败。增加了memcpy解决。 4.wrong answer 在judge函数中当出现多个结点度为0的时候还需要继续判冲突而不能直接return
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
AB
AC
BC
CD
BD
AB
3 2
AB
BA
26 1
AZ
0 0Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.#includecstdio
#includestring.h
#includealgorithm
using namespace std;
int ans,m,n;
char top[50];
int s[50],t[50];//t数组记录v赢了几次,s数组保留赢的次数
int book[50][50];
int mark[30];
int tuopu()
{int l0,flag0;for(int h1; hans; h){int k-1,num0;for(int i1; in; i){if(mark[i]s[i]0)//字母出现过,但是一次也没赢{ki;num;}}if(k-1)return -1;if(num!1)flag1;s[k]-1;top[l]A(k-1);l;for(int i1; in; i){if(book[k][i])s[i]--;}}top[l]0;if(ansnflag0)return 1;return 0;
}
int main()
{while(~scanf(%d%d,n,m)(nm))//n个字母,m组关系{ans0;int flag0;char c[10];memset(t,0,sizeof(t));memset(mark,0,sizeof(mark));//标记字母是否出现过memset(book,0,sizeof(book));for(int i1; im; i){scanf(%s,c);if(flag1)//已找到目标情况continue;int uc[0]-A1;int vc[2]-A1;if(mark[u]0){mark[u]1;ans;}if(mark[v]0){mark[v]1;ans;}if(book[u][v]0){t[v];book[u][v]1;for(int j0; j30; j)s[j]t[j];//将赢的次数保留下来int atuopu();if(a-1)//有环{printf(Inconsistency found after %d relations.\n,i);flag1;}else if(a1)//有序{printf(Sorted sequence determined after %d relations: %s.\n,i,top);flag1;}}}if(flag0)printf(Sorted sequence cannot be determined.\n);}return 0;
}
