DAG 的深度优先搜索标记
/*==================================================*\
| 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<n; ++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;
}