/*
给定一组偏序关系，问最少第几步能确定次序
如果出现环，问第几步出现环
因为要求第几步确定次序或者第几步出现环，所以每次读入一个偏序关系就进行一次拓扑排序
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N =
50;
int in[N];
//入度
bool Map[N][N];
//临接矩阵此题可以随便用
char out[N];
//拓扑排序输出数组
int topsort(
int n ) {
priority_queue<
int,vector<
int>,greater<
int> > q;
//优先队列忠实粉丝
int flag =
0,k;
int zeroflag =
0;
int num =
0,temp[N];
memcpy(temp,in,
sizeof(
in));
//拷贝
for(
int i =
0; i < n; i++
) {
if( !
in[i] ) q.push(i);
}
while( !
q.empty() ) {
if( q.size() >
1 )
zeroflag =
1;
//要注意在while里面判断 因为此过程中也可能出现入度0不止一个的情况
k =
q.top();
q.pop();
num++
;
out[num] = k +
'A';
//num计数 以存到out里面
for(
int i =
0; i < n; i++
)
if(Map[k][i]==
1 && --temp[i] ==
0)
q.push(i);
}
if( num != n )
return 1;
if( zeroflag ==
1 )
return 0;
//多个点入度为零
return -
1;
}
int main(){
int n,m,k;
int step;
//记录操作数
int circleflag,orderflag;
char s[
6];
while( scanf(
"%d%d", &n, &m) != EOF &&
n ){
circleflag=
0;orderflag=
0;
memset(Map,0,
sizeof(Map));
memset(in,
0,
sizeof(
in));
for(
int i =
1; i <= m; i++
){
scanf("%s", s);
if( circleflag ==
0 && orderflag ==
0 ){
//已经判出了 就不读了
if(Map[s[
2]-
'A'][s[
0]-
'A'] ==
1){
circleflag=
1;
//有环了
printf(
"Inconsistency found after %d relations.\n", i);
continue ;
}
if(Map[s[
0]-
'A'][s[
2]-
'A'] ==
0){
Map[s[0]-
'A'][s[
2]-
'A'] =
1;
in[s[
2]-
'A']++
;
}
k =
topsort(n);
if( k ==
1 ){
circleflag=
1;
printf("Inconsistency found after %d relations.\n", i);
}
else if( k == -
1 ){
orderflag=
1;
step=i;
//记录位置
}
}
}
if(circleflag ==
0 && orderflag ==
0)
printf("Sorted sequence cannot be determined.\n");
else if(orderflag ==
1){
printf("Sorted sequence determined after %d relations: ", step);
for(
int i=
1; i<=n; i++
)
printf("%c",
out[i]);
printf(".\n");
}
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10451406.html
