【问题描述】
某旅游公司组团去迪拜世界岛旅游。世界岛由n个岛屿组成，岛屿序号为1～n，这些岛屿都直接或间接相连。岛屿之间用桥梁连接。现从1号岛屿开始游览，并约定按如下方式游览：
1) 每游览完一个岛屿，接下来游览与该岛屿有桥梁直接连接的、未游览过的岛屿。如果存在多个邻接的岛屿，则优先选择序号最小的岛屿。如果该岛屿没有未游览过的相邻岛屿，则返回到该岛屿的上一个岛屿。
2) 每个岛屿都不会重复游览。
另外，对每个岛屿，定义两个时间：
1) 到达该岛屿的时间dfn1；
2) 离开该岛屿的时间dfn2；
时间从1开始计起，游览岛屿的时间不计，每到达一个岛屿，时间加1。如果到达某岛屿后由于没有未游览过的相邻岛屿而随即马上离开，则离开时时间也要加1，详见测试数据。
【输入形式】
输入文件中包含多个测试数据。每个测试数据的第一行为两个正整数n和m，2≤n≤20，分别表示岛屿数和桥梁数；接下来有m行，每行描述了一座桥梁，用该桥梁连接的两个岛屿序号表示；没有连接某个岛屿自身的桥梁，且任何两个岛屿之间最多有一座桥。输入文件最后一行为0 0，表示输入结束。
【输出形式】
对输入文件中的每个测试数据，输出两行，第1行为n个整数，用空格隔开，为第1～n个顶点的时间dfn1；第1行为n个整数，用空格隔开，为第1～n个顶点的时间dfn2。
【样例输入】
7 8
1 4
1 6
1 7
2 3
2 7
3 5
3 6
5 6
0 0
【样例输出】
1 6 5 2 10 4 714 9 12 3 11 13 8
【分析】
题目不是很难，主要是把节点信息读入，然后利用dfs，关键是在过程中需要理清各节点d1和d2的关系。
【代码】
#include <stdio.h>
#include <iostream>
using namespace std;
struct land {
int d1;//登岛时间
int d2;//离岛时间
};
bool maze[][];
bool vist[];
land a[];//记录实践
int n, m;//岛数 桥数
int length;
int dfs(int c) {
a[c].d2 = a[c].d1;
int i = ;
int t = ;
for (i = ; i <= n&&length; i++) {
if (vist[i] == && maze[c][i] == ) {
vist[i] = ;
length--;//未访问的岛数量减一
a[i].d1 = a[c].d2 + ;
a[c].d2 = dfs(i);
t = i;//记录此岛最后一个子岛
}
} //子岛访问完毕，开始回退
if (t == )
a[c].d2 = a[c].d1 + ;//没有下一个可以旅行的岛
else {
a[c].d2 = a[t].d2 + ;
return a[c].d2;
}
return a[c].d2;
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int i = ;
int j = ;
int z = ;
while (cin >> n >> m) {
if (n == && m == )
break;
for (i = ; i <= n; i++) {
for (j = ; j <= n; j++) {
maze[i][j] = ;
}
a[i].d1 = ;
a[i].d2 = ;
vist[i] = ;
}
while (m > ) {
int x;
int y;
cin >> x >> y;
maze[x][y] = ;
maze[y][x] = ;
m--;
}
//dfs
a[].d1 = ;
vist[] = ;
length = n - 1;
dfs(); //输出答案
if (z != )
printf("\n");
for (i = ; i <= n; i++) {
printf("%d", a[i].d1);
if (i + <= n)
printf(" ");
}
printf("\n");
for (i = ; i <= n; i++) {
printf("%d", a[i].d2);
if (i + <= n)
printf(" ");
}
z++;
}
return ;
}
有不懂的地方，或是有自己的想法，欢迎在下面留言！