转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1299234850 提示：拓扑排序
这道题有隐含这一信息，每输入一对关系，如果判定有结果，则可以忽略后面输入数据，即使后面输入数据能改变结果，也不用管。所以应该每输入一个关系就去更新当前的图，然后进行一趟拓扑排序。一旦产生结果，再对后面的数据处理下，就可以输出结果。
所有可能的情况罗列: （独家经验原创，重中之重！可以说没有这些，这题就无法AC！） 一、当输入的字母全部都在前n个大写字母范围内时：
（1） 最终的图 可以排序：
在输入结束前如果能得到最终的图（就是用这n个字母作为顶点，一个都不能少）；
而且最终得到的图 无环；
只有唯一一个 无前驱（即入度为0）的结点，但允许其子图有多个无前驱的结点。
在这步输出排序后，不再对后续输入进行操作
（2）输出矛盾
在输入结束前如果最终图的子图有环
在这步输出矛盾后，不再对后续输入进行操作
（3）输出无法确认排序
这种情况必须全部关系输入后才能确定，其中又有2种可能
①最终图的字母一个不缺，但是有多个 无前驱结点
②输入结束了，但最终的图仍然字母不全，与 无前驱结点 的多少无关
二、当输入的字母含有 非前n个大写字母 的字母时（超出界限）：
（1） 输出矛盾
输入过程中检查输入的字母（结点），若 前n个大写字母 全部出现，则在最后一个大写字母出现的那一步 输出矛盾
（2） 输出无法确认排序
最后一步输入后，前n个大写字母 仍然未全部出现，则输出 无法确认排序
PS：在使用“无前驱结点”算法时必须要注意，在“矛盾优先”的规律下，必须考虑一种特殊情况，就是多个无前驱结点与环共存时的情况，即输入过程中子图都是有 多个无前驱结点，最后一步输入后出现了环，根据算法的特征，很容易输出“不能确认排序”，这是错的，必须适当修改算法，输出“矛盾”。
例如：
6 6
A
B
C
F
D
E
输出矛盾
1 //Memory Time 2 //276K 0MS 3 4 #include 5 using namespace std; 6 7 int n,m; //n结点下限，m关系对 8 char top_out[26]; //排序输出列表 9 int po=0; //输出列表的指针 10 11 typedef class degree 12 { 13 public: 14 int in; //入度 15 char to[26]; //记录指向的所有顶点，以便删除出度的操作 16 int pt; //数组to的指针 17 }; 18 19 int top_sort(degree alph[],bool mark[],int num) 20 { 21 /*假设图G的当前子图为F*/ 22 23 memset(top_out,'\0',sizeof(top_out)); 24 po=0; 25 26 int del_n=0; 27 int zero=0; //记录图F中入度为0的结点个数 28 for(int i='A';i<'A'+n;i++) 29 if(mark[i] && !alph[i].in) 30 zero++; 31 32 bool flag=false; 33 while(zero>0) 34 { 35 if(zero>1) //图F的无前驱结点的个数不唯一，排序无法确定 36 flag=true; //考虑到"矛盾"的优先性，避免在多个0入度结点情况下，最后一步输入刚好出现环（此时为矛盾） 37 //所以这里先不返回值，而是先标记，执行拓扑，根据情况决定返回值 38 39 for(int k='A';k<='A'+n;k++) //寻找图F的唯一的前驱结点 40 if(mark[k] && !alph[k].in) 41 { 42 mark[k]=false; //删除图F的唯一无前驱结点k 43 del_n++; //记录删除的结点数 44 top_out[po++]=k; //k记录到排序输出列表 45 for(int i=0;i>n>>m; 78 79 if(!n||!m) 80 break; 81 82 /*Initial*/ 83 84 memset(mark,false,sizeof(mark)); 85 memset(mark_t,false,sizeof(mark_t)); 86 num=0; 87 88 for(int k='A';k<'A'+n;k++) 89 { 90 alph[k].in=alph_t[k].in=0; 91 alph[k].pt=alph_t[k].pt=0; 92 memset(alph[k].to,'\0',sizeof(alph[k].to)); 93 memset(alph_t[k].to,'\0',sizeof(alph_t[k].to)); 94 } 95 96 /*Structure Maps*/ 97 98 char x,symbol,y; //临时变量 99 bool flag=false;
100 bool sign=false;
101 int value; //记录拓扑返回的值
102 int step; //记录当前情况发生的步骤
103 for(int pair=1;pair<=m;pair++)
104 {
105 cin>>x>>symbol>>y;
106 107 if(x>='A'+n || y>='A'+n) //当输入的结点不在前n个字母范围内时
108 sign=true; //不再进行拓扑,单纯检查后续输入是否把前n个字母都输入了
109 //为了区分非前n个字母的字母的输入时间，是在确认了排序或矛盾之前还是之后
110 //在确认 排序或矛盾之前:flag=false,sign=true
111 //在确认 排序或矛盾之后:flag=true,sign=true
112 113 if(!mark[x] && x<'A'+n)
114 num++;
115 if(!mark[y] && y<'A'+n)
116 num++;
117 118 if(!flag && !sign)
119 {
120 value=0;
121 122 mark[x]=mark[y]=true; //顶点标记
123 mark_t[x]=mark_t[y]=true;
124 125 alph[y].in++; //入度标记
126 alph_t[y].in++;
127 128 alph[x].to[ alph[x].pt++ ]=y; //指向标记 & 指针移动
129 alph_t[x].to[ alph_t[x].pt++ ]=y;
130 131 /*Top-Sort & Sign*/
132 133 value=top_sort(alph_t,mark_t,num); //每次输入后图都被更新，要重新拓扑
134 if(value==1) //排序确认
135 {
136 step=pair; //记录确认排序的位置
137 flag=true; //不再对后续输入处理
138 }
139 else if(value==2) //矛盾
140 {
141 step=pair; //记录矛盾发生的位置
142 flag=true; //不再对后续输入处理
143 }
144 else if(value==3 && pair
延伸阅读
最新评论