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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
