Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1109????Accepted Submission(s): 275
?????? 本題對本人來說絕對是一個挑戰,因為以前我從來沒有寫過拓撲排序也沒用過set,這是我第一次的嘗試,雖然wrong了很多次花費了一整天的時間,但還是應當值得紀念的。本題的思想就是拓撲排序+并查集。
???? 注意事項:
??? (1)因為本題數據比較大,用鄰接矩陣存儲太浪費空間了,我就因此而超內存好幾次,建議使用鄰接表。特別是對這種稀疏矩陣,采用鄰接表即可節約空間又可節約時間
???? (2)一定要找完才能判斷,如果同時又CONFLICT和UNCERTAIN輸出CONFLICT
???? (3)使用并查集一定要小心,如果對某個節點操作一定要轉化為對根節點的操作,因為本題的思想就是用并查集把相同放到一個集合看成是一個節點。
? 代碼:
??
?
1 #include < iostream >
2 #include < set >
3 ? using namespace std;
4 typedef struct t
5 {
6 int data;
7 struct t * next;
8 }T;
9 ? struct node
10 {
11 int in ;
12 int root;
13 struct t * next;
14 bool operator < ( const node & a) const
15 {
16 if (a. in == in )
17 return a.root > root;
18 else return a. in > in ;
19 }
20 }s[ 10005 ];
21 ? int father[ 10005 ],rank[ 10005 ],a1[ 10005 ],c1[ 10005 ]; char d[ 10005 ];
22 ? void insert( int a, int c)
23 {
24 node * t =& s[a];
25 T * x = (T * )malloc( sizeof (T));
26 s[c]. in ++ ;
27 x -> data = c;
28 x -> next = t -> next;
29 t -> next = x;
30 }
31 int find( int x)
32 {
33 if (x != father[x])
34 father[x] = find(father[x]);
35 return father[x];
36 }
37 void Union( int x, int y)
38 {
39 x = find(x);
40 y = find(y);
41 if (x == y)
42 return ;
43 if (rank[x] > rank[y])
44 {
45 father[y] = x;
46 }
47 else
48 {
49 if (rank[x] == rank[y])
50 rank[y] ++ ;
51 father[x] = y;
52 }
53 }
54 int main()
55 {
56 set < node > se;
57 node cur1,cur2;
58 int n,m,i,a,c,k,j,mark1,mark2; char b;
59 while (scanf( " %d%d " , & n, & m) != EOF)
60 {
61 j = 0 ;
62 se.clear ();
63 for (i = 0 ;i < n;i ++ )
64 {
65 father[i] = i;
66 s[i]. in = 0 ;
67 s[i].next = NULL;
68 s[i].root = i;
69 rank[i] = 0 ;
70 }
71 for (i = 1 ;i <= m;i ++ )
72 {
73 scanf( " %d " , & a);
74 getchar();
75 scanf( " %c " , & b);
76 scanf( " %d " , & c);
77 if (b == ' = ' )
78 Union(a,c);
79 else
80 {
81 j ++ ;
82 d[j] = b;
83 a1[j] = a;
84 c1[j] = c;
85 }
86 }
87 for (k = 1 ;k <= j;k ++ )
88 if (d[k] == ' > ' )
89 {
90 a = find(a1[k]);c = find(c1[k]);insert(a,c);
91 }
92 else
93 {
94 a = find(a1[k]);c = find(c1[k]);insert(c,a);
95 }
96
97 for (i = 0 ;i < n;i ++ )
98 se.insert (s[find(i)]);
99 mark1 = 0 ;mark2 = 0 ;
100 set < node > ::iterator it1;
101 set < node > ::iterator it2;
102 while ( ! se.empty ())
103 {
104 it1 = se.begin();
105 if (( * it1). in != 0 )
106 {
107 mark1 = 1 ;
108 cout << " CONFLICT " << endl;
109 break ;
110 }
111 T * t;
112 t = ( * it1).next;
113 se.erase(se.begin ());
114 if (se.empty ())
115 break ;
116 it2 = se.begin ();
117 if (( * it2). in == 0 )
118 {
119 mark2 = 1 ;
120 }
121 while (t != NULL)
122 {
123 se.erase (s[t -> data]);
124 s[t -> data]. in -- ;
125 se.insert(s[t -> data]);
126 t = t -> next;
127 }
128 }
129 if (mark1 == 0 )
130 if (mark2 == 1 )
131 cout << " UNCERTAIN " << endl;
132 else
133 cout << " OK " << endl;
134 }
135 return 0 ;
136 }
137
138
139
140
141
142
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
