Description:
规定对于一个只有大写字母的字符串是有大小顺序的。如ABCD.即A<B。B<C。C<D。那么问题来了。现在第一行给你n， m代表序列里只会出现前n的大写字母、以后的第2到m行给你m组。有三个字符。即“第一个字符” “<”"第二个字符"...请你给出答案。在第几组之后确定了排列顺序或者第几组之后出现矛盾。还是直到输入结束也没有排列顺序也没有出现矛盾。
思路很简单、就是把前n个字符转换成0~n-1的数字。然后，，每次输入都要拓扑一次。如果出现了固定顺序或者矛盾。以后就可以只输有输入操作了。如果直到最后这两种情况都没有出现的话。就是无法确定。
附代码：WA了好久。。仍然有地方不懂。。但是是人家自己敲得啦，，，~~~~(>_<)~~~~
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int map[27][27];
int degree[27];
int top[27];
int tot;
int n, m;
queue<int>q;
void init()
{
tot = 0;
memset(map, 0, sizeof(map));
memset(degree, 0, sizeof(degree));
memset(top, 0, sizeof(top));
}
int topsort()
{
int l = 0;
int flag = 0;
while(!q.empty())
q.pop();
int dd[30];
memcpy(dd, degree, sizeof(degree));
for (int i=0; i<n; ++i)
{
if (dd[i] == 0)
{
q.push(i);
}
}
while(!q.empty())
{
if (q.size() > 1)
flag = 1;
int k = q.front();
q.pop();
top[l++] = k;
for (int i=0; i<n; ++i)
{
if (map[k][i] == 1)
{
if (--dd[i] == 0)
q.push(i);
}
}
}
if (l != n)
return 2;
else if (flag == 1)
return 1;
// T_T 为什么必须先判断是不是有矛盾。再判断是不是无法确定呢。也就是。有时候同时有两个入度为0的点。并不能说明就是无法判断。
//所以不能在flag == 1处。改为直接return 1.....
// if (flag == 1)
// return 1;
// else if (l != n)
// return 2;
return 0;
}
int main()
{
char a, b, temp;
int i, j;
int aa, bb;
int mao, que;
int now = 0;
while(cin >> n >> m)
{
init();
if (n == 0 && m == 0)
break;
mao = 0;
que = 0;
now = 0;
for (i=0; i<m; ++i)
{
cin >> a >> temp >> b;
now++;
if (!mao && !que)
{
if (map[b-'A'][a-'A'] == 1)
{
mao = 1;
cout << "Inconsistency found after " << now << " relations.
";
continue;
}
if (map[a-'A'][b-'A'] == 0)
{
map[a-'A'][b-'A'] = 1;
degree[b-'A']++;
}
int res = topsort();
if (res == 0)
{
cout << "Sorted sequence determined after " << now << " relations: ";
for (int j=0; j<n; ++j)
{
cout << char(top[j] + 'A');
}
cout << ".
";
que = 1;
}
else if (res == 2)
{
cout << "Inconsistency found after " << now << " relations.
";
mao = 1;
}
}
}
if (!mao && !que)
{
cout << "Sorted sequence cannot be determined.
";
}
}
return 0;
}