nyoj349 http://acm.nyist.net/JudgeOnline/problem.php?pid=349
poj1094 http://poj.org/problem?id=1094
这两个题是一样的，不过在poj上A了才算真的过，ny上数据有一点弱。
题目大意输入n，m。 一共有n个字母（从A开始）， m行语句每个语句“x﹤y”，说明x，y之间的偏序关系。让你判断是否可以通过这些关系得到一个唯一的升序序列，若能则输出这个序列并指出通过前多少条语句得出的，如果n个字母间存在矛盾，输出相应语句并指出那条语句开始出现矛盾的。如果没有唯一序列又不存在矛盾就输出想应信息。
分析：
所用算法拓扑排序：使有向图G的每一条边（u，v）对应的u都排在v的前面。不难发现如果图中存在又向环，则不存在拓扑排序。拓扑排序答案可能有多个（例如：a﹤b; c﹤b; d﹤c; 排序可为adcb或dacb）,但此题中要求排序唯一。
首先我们可以把每组小于关系看成是一个又向边，这样我们还会得到一个又向图，我们所要做的就是把图中所有点排序，因为需要知道在哪出现矛盾，在哪可以得到唯一排序的，那么我们就每输入一个边（小于关系）就更新一次图，做一回拓扑排序，看是否能得到唯一排序、有矛盾。如果所有边都结束了还没有矛盾，那就看看排序是否唯一。
在排序的时候我们需要记录每个点u所排的位置（小的排在前面），已知的由u为出发点的边可能有多个（也就是已给出多个“u﹤xi”的偏序关系），那么u点所拍的位置就是所有xi中的最小值-1。
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
//v[i]标记第i个字母是否dfs过， sum[i]存储排在第i位的字母有几个（用来判断排序是否唯一）
int n, m, v[], a[], sum[], k[];
vector<int> vec[];
struct egde
{
int x, y;
}e[];
int dfs(int x)
{
int flag = ;
v[x] = -;//正在搜索的点标记为-1
int mi = n+;
for(int i = ; i < vec[x].size(); i++)
{
flag = ;
int y = vec[x][i];
if(v[y] < ) return ;
else if(v[y] == )
{
if(dfs(y) == )
return ;
else
mi = min(mi, a[y]);
}
mi = min(mi, a[y]);
}
v[x] = ;//搜索过的点标记为1
//a[x]记录字母x排在第几位
if(flag == )//flag=1说明有已知比他大的点， x就排在 所有比它大的点的最小位置 的前面
a[x] = mi - ;
else a[x] = n;//flag= 0，说明x是已知最大的点之一，排在最后一位n位
return ;
}
int topu()
{
memset(v, , sizeof(v));
for(int i = ; i <= n; i++) a[i] = n+;//初始化所有点的排序位置为n+2;
for(int i = ; i <= n; i++)
{
if(v[i] == && vec[i].size() != )
{
int tem = dfs(i);
if(tem == ) return ;
}
}
return ;
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF && n && m)
{
for(int i = ; i <= m; i++)
{
char a, b, c;
int tem;
cin >> a >> c >> b;
tem = a - 'A' + ; e[i].x = tem;//e[i]存储第i条边的两个点
tem = b - 'A' + ; e[i].y = tem;
}
int error = -;
int flag;//标记排序是否为为一
for(int i = ; i <= n; i++) {vec[i].clear();}
for(int i = ; i <= m; i++)
{
flag = ;
vec[e[i].x].push_back(e[i].y);//不断加入边， 每次加边都跟新存出边的vec；
error = topu();//每次加边都进行一次拓扑排序， 返回值=0时，存在矛盾， 返回值=1时没有矛盾
if(error == )//error = 0， 则有矛盾
{
printf("Inconsistency found after %d relations.\n", i);
break;
}
else if(error == )
{
memset(sum, , sizeof(sum));
flag = ;
for(int i = ; i <= n; i++)
{
if(a[i] == n + )//当字母i排在第n+2位时，说明字母i没由与它连接的边，
{
flag = ;continue;
}
sum[a[i]]++;//sum[i]存储排在第i位的字母有几个（用来判断排序是否唯一）
k[a[i]] = i;//k[i]记录排在第i位的字母
if(sum[a[i]] > ){flag = ; break;}//如果排在同一位置的字母不止一个，则有矛盾
}
if(flag == )//若所有点都有与之连接的边，并且字母所拍的位置不重复则说明排序唯一
{
printf("Sorted sequence determined after %d relations: ", i);
for(int i = ; i <= n; i++)
printf("%c", k[i] + 'A' - );
printf(".\n");
break;
}
}
}
if(flag == )//若不存在矛盾， 但是字母的所排位置有重复，则说明排序不唯一
printf("Sorted sequence cannot be determined.\n");
}
return ;
}