Posted on 2008-04-03 18:16
superman 閱讀(339)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1060 C++ 00:00.06 848K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 class Graph
8 {
9 private:
10 int n, e;
11 int count[26];
12 bool map[26][26];
13 public:
14 Graph(const int nn)
15 {
16 n = nn; e = 0;
17 memset(count, 0, sizeof(count));
18 memset(map, false, sizeof(map));
19 }
20 void AddEdge(const int s, const int t)
21 {
22 e++;
23 if(map[s][t] == false)
24 count[t]++;
25 map[s][t] = true;
26 }
27 bool TopSort(int x[])
28 {
29 int cn = n;
30 int cnt[26];
31 memcpy(cnt, count, sizeof(count));
32
33 while(cn--)
34 {
35 int tot = 0, index;
36 for(int i = 0; i < n; i++)
37 if(cnt[i] == 0)
38 {
39 index = i;
40 tot++;
41 }
42 if(tot > 1)
43 return 0;
44 if(tot == 1)
45 {
46 for(int i = 0; i < n; i++)
47 if(map[index][i])
48 cnt[i]--;
49 x[cn] = index;
50 cnt[index] = -1;
51 }
52 }
53 return 1;
54 }
55 bool ExistCycle()
56 {
57 bool f[26][26];
58 memcpy(f, map, sizeof(map));
59 for(int k = 0; k < n; k++)
60 for(int i = 0; i < n; i++)
61 for(int j = 0; j < n; j++)
62 if(f[i][k] && f[k][j])
63 f[i][j] = 1;
64 for(int i = 0; i < n; i++)
65 if(f[i][i])
66 return 1;
67 return 0;
68 }
69 };
70
71 int main()
72 {
73 int n, m;
74 string relation;
75 while((cin >> n >> m) && n && m)
76 {
77 Graph G(n);
78 bool find = false;
79 for(int i = 1; i <= m; i++)
80 {
81 cin >> relation;
82
83 if(find)
84 continue;
85
86 G.AddEdge(relation[0] - 'A', relation[2] - 'A');
87
88 if(G.ExistCycle())
89 {
90 cout << "Inconsistency found after " << i << " relations." << endl;
91 find = true;
92 continue;
93 }
94
95 int x[26];
96 if(G.TopSort(x))
97 {
98 cout << "Sorted sequence determined after " << i << " relations: ";
99 for(int i = n - 1; i >= 0; i--)
100 cout << char(x[i] + 'A');
101 cout << '.' << endl;
102 find = true;
103 }
104 }
105 if(find == false)
106 cout << "Sorted sequence cannot be determined." << endl;
107 }
108
109 return 0;
110 }
111