nyoj349 poj1094 Sorting It All Out(拓撲排序)，nyoj349poj1094
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[30], a[30], sum[30], k[30];
vector<int> vec[30];
struct egde
{
int x, y;
}e[10010];
int dfs(int x)
{
int flag = 0;
v[x] = -1;//正在搜索的點標記為-1
int mi = n+1;
for(int i = 0; i < vec[x].size(); i++)
{
flag = 1;
int y = vec[x][i];
if(v[y] < 0) return 0;
else if(v[y] == 0)
{
if(dfs(y) == 0)
return 0;
else
mi = min(mi, a[y]);
}
mi = min(mi, a[y]);
}
v[x] = 1;//搜索過的點標記為1
//a[x]記錄字母x排在第幾位
if(flag == 1)//flag=1說明有已知比他大的點， x就排在 所有比它大的點的最小位置 的前面
a[x] = mi - 1;
else a[x] = n;//flag= 0，說明x是已知最大的點之一，排在最後一位n位
return 1;
}
int topu()
{
memset(v, 0, sizeof(v));
for(int i = 1; i <= n; i++) a[i] = n+2;//初始化所有點的排序位置為n+2;
for(int i = 1; i <= n; i++)
{
if(v[i] == 0 && vec[i].size() != 0)
{
int tem = dfs(i);
if(tem == 0) return 0;
}
}
return 1;
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF && n && m)
{
for(int i = 1; i <= m; i++)
{
char a, b, c;
int tem;
cin >> a >> c >> b;
tem = a - 'A' + 1; e[i].x = tem;//e[i]存儲第i條邊的兩個點
tem = b - 'A' + 1; e[i].y = tem;
}
int error = -1;
int flag;//標記排序是否為為一
for(int i = 1; i <= n; i++) {vec[i].clear();}
for(int i = 1; i <= m; i++)
{
flag = 1;
vec[e[i].x].push_back(e[i].y);//不斷加入邊， 每次加邊都跟新存出邊的vec；
error = topu();//每次加邊都進行一次拓撲排序， 返回值=0時，存在矛盾， 返回值=1時沒有矛盾
if(error == 0)//error = 0， 則有矛盾
{
printf("Inconsistency found after %d relations.\n", i);
break;
}
else if(error == 1)
{
memset(sum, 0, sizeof(sum));
flag = 1;
for(int i = 1; i <= n; i++)
{
if(a[i] == n + 2)//當字母i排在第n+2位時，說明字母i沒由與它連接的邊，
{
flag = 0;continue;
}
sum[a[i]]++;//sum[i]存儲排在第i位的字母有幾個（用來判斷排序是否唯一）
k[a[i]] = i;//k[i]記錄排在第i位的字母
if(sum[a[i]] > 1){flag = 0; break;}//如果排在同一位置的字母不止一個，則有矛盾
}
if(flag == 1)//若所有點都有與之連接的邊，並且字母所拍的位置不重復則說明排序唯一
{
printf("Sorted sequence determined after %d relations: ", i);
for(int i = 1; i <= n; i++)
printf("%c", k[i] + 'A' - 1);
printf(".\n");
break;
}
}
}
if(flag == 0)//若不存在矛盾， 但是字母的所排位置有重復，則說明排序不唯一
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
View Code
