?
#include?
<
iostream
>
using
?
namespace
?std;
const
?
int
?MAXN?
=
?
100
;
int
?list[MAXN][MAXN];
//
鄰接表?
int
?next[MAXN];
int
?vInDegree[MAXN];?
//
定點(diǎn)入度?
int
?tpV[MAXN];?
//
拓?fù)湫蛄?/span>
int
?n;?
//
?定點(diǎn)數(shù)?
int
?TopoSort()
{
????
//
不能求最大并行組?
????
//
使用靜態(tài)鏈盞
????
int
?i,?t;
????
int
?cnt?
=
?
0
;
????
int
?top?
=
?
-
1
;?
????
for
?(i
=
0
;?i
<
n;?i
++
)?
{
????????
if
?(vInDegree[i]?
==
?
0
)?
{?
//
進(jìn)盞?
????????????vInDegree[i]?
=
?top;
????????????top?
=
?i;
????????}
????}
????
while
?(top?
>=
?
0
)?
{
????????t?
=
?top;
????????top?
=
?vInDegree[top];?
//
出盞?
????????tpV[cnt
++
]?
=
?t;
????????
for
?(i
=
0
;?i
<
next[t];?i
++
)?
{
????????????vInDegree[list[t][i]]
--
;
????????????
if
?(vInDegree[list[t][i]]?
==
?
0
)?
{?
//
進(jìn)盞?
????????????????vInDegree[list[t][i]]?
=
?top;
????????????????top?
=
?list[t][i];
????????????}
????????}
????}
????
return
?cnt;
}
int
?main()
{
????
int
?i,?j,?b;
????freopen(
"
test.txt
"
,?
"
r
"
,?stdin);
????scanf(
"
%d
"
,?
&
n);
????memset(vInDegree,?
0
,?
sizeof
(vInDegree));
????
for
?(i
=
0
;?i
<
n;?i
++
)?
{
????????scanf(
"
%d
"
,?
&
b);
????????scanf(
"
%d
"
,?
&
next[b]);
????????
for
?(j
=
0
;?j
<
next[b];?j
++
)?
{
????????????scanf(
"
%d
"
,?
&
list[b][j]);
????????????vInDegree[list[b][j]]
++
;
????????}
????}
????
if
?(TopoSort()?
==
?n)?
{
????????
for
?(i
=
0
;?i
<
n;?i
++
)?
????????????printf(
"
%d?
"
,?tpV[i]);
????????printf(
"
\n
"
);
????}
?
else
?
{
????????printf(
"
can't?not?be?Sort!\n
"
);
????}
????
//
system("pause");
????
return
?
0
;
}
?
posted on 2006-10-11 13:05
豪 閱讀(1404)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法