題目描述:
給出m個關系,n個元素, 問最早出現唯一拓撲序/環的位置.
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1060
算法分析:
拓撲排序, 要優先判斷是否有環的情況, 然后再判斷是否有唯一拓撲序.
zoj 1060
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 char ch[50];
6 int n, m, du[30],G[30][30],tmp[30],vis[30];
7 int solve(){
8 memcpy(tmp,du,sizeof(du));
9 memset(vis,0,sizeof(vis));
10 int flag = 1;
11 for(int i = 0; i <n; i++){
12 int s = -1, cnt = 0;
13 for(int j= 0; j < n; j++)
14 if(!vis[j] && !tmp[j]){
15 s = j; cnt ++;
16 }
17 // cout<<s << " "<<cnt<<endl;
18 if(cnt != 1){
19 flag = cnt;
20 if(flag == 0)
21 break;
22 }
23 ch[i] = 'A' + s;
24 vis[s] = 1;
25 for(int j= 0; j< n; j++)
26 if(!vis[j] && G[s][j]) tmp[j] --;
27 }
28 ch[n] = 0;
29 if(flag == 0) return 0;
30 if(flag == 1) return 1;
31 return 2;
32 }
33 int main(){
34 while(~scanf("%d%d",&n,&m), n) {
35 memset(G,0,sizeof(G));
36 memset(du,0,sizeof(du));
37 int s = 2,flag = 0;;
38 for(int i = 0; i < m; i++){
39 // cout<<"i: "<<i<<endl;
40 scanf("%s",ch);
41 if(flag) continue;
42 int u = ch[0] - 'A';
43 int v = ch[2] - 'A';
44 G[u][v] = 1;
45 du[v] ++;
46 s = solve();
47 if(s == 2) continue;
48 if(s == 1) {
49 printf("Sorted sequence determined after %d relations: %s.\n",i+1,ch);
50 flag = 1;
51 }
52 else {
53 printf("Inconsistency found after %d relations.\n",i+1);
54 flag = 1;
55 }
56 }
57 if(s == 2) {
58 puts("Sorted sequence cannot be determined.");
59 }
60 }
61 return 0;
62 }
63 posted on 2012-09-06 14:18
西月弦 閱讀(260)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告