/*==================================================*\
| DAG
的深度优先搜索标记
| INIT: edge[][]
邻接矩阵
; pre[], post[], tag
全置
0;
| CALL: dfstag(i, n); pre/post:
开始
/
结束时间
\*==================================================*/
int
edge[V][V], pre[V], post[V], tag;
void
dfstag(
int
cur,
int
n)
{
// vertex: 0 ~ n-1
pre[cur] = ++tag;
for
(
int
i=0; i
if
(edge[cur][i]) {
if
(0 == pre[i]) {
printf(
"Tree Edge!\n"
);
dfstag(i, n);
}
else
{
if
(0 == post[i]) printf(
"Back Edge!\n"
);
else if
(pre[i] > pre[cur])
printf(
"Down Edge!\n"
);
else
printf(
"Cross Edge!\n"
);
}
}
post[cur] = ++tag;
}