題意描述:
給定字母表的前n個大些字母,以及這些字母間兩兩之間的大小關系(這樣的關系給定m組),問由這m組關系能否確定n個字母的整體順序,如果能輸出按續排列的字母。
顯然,本題就是拓撲排序,不過題目的要求使得我們要處理一些細節。
下面我先說以下拓撲排序:
嚴蔚敏《數據結構》上的定義是:
由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較,而全序指集合中全體成員之間均可比較。
舉個例子,一個大的工程通常有許多小的工程組成,這些小工程之間通常存在某些先后順序;當然有些小工程之間不存在先后關系,它們是可以并行的。如果兩個小工程直接或間接的相互依賴,就是兩個小工程互為對方的先行條件,整個工程將無法進行下去。用一個個頂點分別表示這些小工程,用有向的邊表示小工程之間的依賴關系,我們可以得到一個有向圖。
拓撲排序可以幫助我們確定這些小工程開始的順序,并且能夠判定小工程之間是否存在相互依賴(圖中是否有回路)。
拓撲排序的具體做法是:
1.在有向圖中選擇一個沒有前驅(入度為0)的頂點,輸出
2.從圖中刪除該頂點和所有以它為尾的弧,并更新相關點的入度
3.重復1,2步,直到所有頂點都被輸出,或者發現圖中存在回路。
如果結合上面所舉的工程的例子,沒有依賴(先后)關系的工程是可以并行的,但是就本題(zoj1060)而言,它要求每兩個點之間的關系都是確定的,是不允許出現并行的,所以,當某一時刻,我們發現入度為0的點不止1個時,排序就失敗了。
本題的輸出分為三種情況,并且要求輸出所用的條件個數,因此每增加一個條件就要做一次拓撲排序。
以下是本題代碼,第一次寫,有點亂,將就一下把~~
測試數據:
http://poj.org/showmessage?message_id=133905

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//zoj1060 poj1094
#define LEN 30
#define LEN_ORDER 10000
typedef struct
{
char a;
char c;
char b;
}Order;
int n, m;
Order od[LEN_ORDER];
int list[LEN];//存儲最終的全序序列
int lstlen;
int indgr0[LEN];//各節點的入度
int indgr1[LEN];//是indgre0[]的副本
int mp[LEN][LEN];
int s[LEN];//記錄該節點是否已排好序,== 1代表已排好
int zr;
int gard, stp;
int findZeroIndgr()// for Topological()
{
int i, j;
int a = -1;
int b = -1;
for(i = 0; i < n; i++)
{
if(s[i] == 0 && indgr1[i] == 0)
{
a = i;
break;
}
}
for(i = i + 1; i < n; i++)
{
if(s[i] == 0 && indgr1[i] == 0)
{
b = i;
break;
}
}
if(a == -1)
return -1;
else if(b != -1)
return 0;
zr = a;
return 1;
}
int Topological()//這次拓撲排序用來確定全序關系
{
int i, j;
for(i = 0; i < n; i++)
{
int t = findZeroIndgr();
if(t == -1 || t == 0)
break;
else
{
list[lstlen++] = zr;
s[zr] = 1;// in set
for(j = 0; j < n; j++)//change in dgree
if(mp[zr][j] == 1)
indgr1[j]--;
}
}
if(lstlen == n)
return 1;
return 0;
}
int findZeroIndgr2()//for Topological2()
{
int i, j;
int a = -1;
for(i = 0; i < n; i++)
{
if(s[i] == 0 && indgr1[i] == 0)
{
a = i;
break;
}
}
if(a == -1)
return 0;
zr = a;
return 1;
}
int Topological2()//這次拓撲排序用來判是否存在回路
{
int i, j;
for(i = 0; i < n; i++)
{
int t = findZeroIndgr2();
if(t == 0)
return 0;
s[zr] = 1;
for(j = 0; j < n; j++)//change in dgree
if(mp[zr][j] == 1)
indgr1[j]--;
}
return 1;
}
int main()
{
int i, j, k;
int a, b;
//FILE *fp = fopen("out.txt", "w");
FILE *fp = stdout;
scanf("%d%d", &n, &m);
while(n + m != 0)
{
getchar();
for(i = 0; i < m; i++)
{
scanf("%c%c%c", &od[i].a, &od[i].c, &od[i].b);
getchar();
}
gard = 2;
memset(mp, 0, sizeof(mp));
memset(indgr0, 0, sizeof(indgr0));
for(i = 0; i < m; i++)// make mp[][]
{
a = od[i].a - 'A';
b = od[i].b - 'A';
if(od[i].c == '<' && mp[a][b] == 0)
{
mp[a][b] = 1;
indgr0[b]++;
}
else if(od[i].c == '>' && mp[b][a] == 0)
{
mp[b][a] = 1;
indgr0[a]++;
}
for(j = 0; j < n; j++)
indgr1[j] = indgr0[j];
memset(s, 0, sizeof(s));
if(Topological2() == 0)//存在回路,結束
{
gard = 3;
stp = i + 1;
break;
}
lstlen = 0;
for(j = 0; j < n; j++)
indgr1[j] = indgr0[j];
memset(s, 0, sizeof(s));
if(Topological() == 1)//求出全序關系
{
gard = 1;
stp = i + 1;
break;
}
}
if(gard == 1)
{
fprintf(fp, "Sorted sequence determined after %d relations: ", stp);
for(j = 0; j < lstlen; j++)
fprintf(fp, "%c", list[j] + 'A');
fprintf(fp, ".\n");
}
else if(gard == 2)
fprintf(fp, "Sorted sequence cannot be determined.\n");
else
fprintf(fp, "Inconsistency found after %d relations.\n", stp);
scanf("%d%d", &n, &m);
}
fclose(fp);
//system("pause");
}
posted on 2012-08-16 19:19
小鼠標 閱讀(1806)
評論(0) 編輯 收藏 引用 所屬分類:
圖論