深度优先搜索算法是一种图的搜索算法。深度优先搜索采用的策略是，尽可能地访问相邻结点，访问到底之后就往回退出，直至栈被清空。
题目是这样子的
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
为此，我们就根据上面的思路来实现。可以使用标准库的stack来保存“仍在搜索中的结点”。这里采用的是邻接矩阵法来表示图，以此实现深度优先搜索。
深度优先搜索的具体操作
1、把搜索的起点压入堆栈
2、循环进行以下的操作：
代码语言：javascript复制（1）访问栈顶的结点u
（2）如果栈顶的结点u还有未被访问的子结点，就访问他们（结点id较小的优先被访问），当结点u没有未被访问的子结点的时候，就将结点u从堆栈中弹出标记每个结点的状态
为了标记每个结点当前的状态，我们可以用三种颜色来描述他们的状态：
白色->未被访问
灰色->正在被访问中
黑色->已经访问结束
下面有个图片很具体的描述了深度优先搜索的过程
分析
使用邻接矩阵的深度优先搜索算法，由于程序要调查每个顶点是否与其他每个顶点相邻，因此时间复杂度为O(n²)。并且，对于规模较大的图，还可能导致堆栈溢出。
用堆栈实现的深度优先搜索
代码语言：javascript复制#include<iostream>
#include<stack>
using namespace std;
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n;
int d[MAX 1],f[MAX 1];//进入时间和退出时间
int M[MAX 1][MAX 1];
int color[MAX 1];
int tt=0;
int nt[MAX 1];//用来存放当前结点访问到的是第几个子结点
int next(int u)
{
for(int v = nt[u];v<=n;v )
{
nt[u] = v 1;
if(M[u][v]) return v;
}
return -1;
}
void dfs_visit(int r)
{
for(int i=0;i<=n;i )
nt[i] = 0;
stack<int>S;
S.push(r);
color[r] = GRAY;
d[r] = tt;
while(!S.empty())
{
int u = S.top();
int v = next(u);
if(v!=-1)
{
if(color[v]==WHITE)
{
color[v] = GRAY;
d[v] = tt;
S.push(v);
}
}
else
{
S.pop();
color[u] = BLACK;
f[u] = tt;
}
}
}
void dfs()
{
for(int i=0;i<=n;i )
color[i] = WHITE;
tt = 0;
//以未访问的结点u为起点进行深度优先搜索。
for(int u=1;u<=n;u )
{
if(color[u] == WHITE) dfs_visit(u);
}
for(int i=1;i<=n;i )
{
cout<<i<<" "<<d[i]<<" "<<f[i]<<endl;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i )
{
int u,k;
cin>>u>>k;
for(int j=0;j<k;j )
{
int v;
cin>>v;
M[u][v] = 1;
}
}
dfs();
}
