#include
<
iostream
>
using
namespace
std;
const
int
MAXN
=
100
;
int
list[MAXN][MAXN];
//
邻接表
int
next[MAXN];
int
vInDegree[MAXN];
//
定点入度
int
tpV[MAXN];
//
拓扑序列
int
n;
//
定点数
int
TopoSort()
{
//
不能求最大并行组
//
使用静态链盏
int
i, t;
int
cnt
=
0
;
int
top
=
-
1
;
for
(i
=
0
; i
<
n; i
++
)
{
if
(vInDegree[i]
==
0
)
{
//
进盏
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
)
{
//
进盏
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
豪 阅读(1390)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法