SDUT 2107 图的深度遍历

图的深度遍历

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。

Input

输入第一行为整数n（0 < n < 100），表示数据的组数。对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m条边，k个顶点。下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

Output

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。

Example Input

Example Output

0 1 2 3

DQE：

纯水题233

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 #define MVN 110
 6 
 7 typedef struct AdjMatrix
 8 {
 9     int w;
10     char *info;
11 }AM;
12 
13 typedef struct MGraph
14 {
15     int vex[MVN];
16     AM arc[MVN][MVN];
17     int vexn,arcn;
18 }MG;
19 
20 void creat(MG &G)
21 {
22     int i,j,k;
23     for(i=0;i<G.vexn;i++)
24         for(j=0;j<G.vexn;j++)
25             G.arc[i][j].w=0;
26     for(k=0;k<G.arcn;k++)
27     {
28         scanf("%d %d",&i,&j);
29         G.arc[i][j].w=G.arc[j][i].w=1;
30     }
31 }
32 
33 void DFS(MG &G,bool *f,int i)
34 {
35     if(i==0)
36         printf("%d",i);
37     else
38         printf(" %d",i);
39     f[i]=true;
40     int k;
41     for(k=0;k<G.vexn;k++)
42         if(G.arc[i][k].w==1&&f[k]==false)
43             DFS(G,f,k);
44 }
45 
46 int main()
47 {
48     int t;
49     scanf("%d",&t);
50     while(t--)
51     {
52         MG G;
53         scanf("%d %d",&G.vexn,&G.arcn);
54         creat(G);
55         bool visited[MVN]={false};
56         DFS(G,visited,0);
57         printf("
");
58     }
59     return 0;
60 }
61 
62 /***************************************************
63 User name: ***
64 Result: Accepted
65 Take time: 0ms
66 Take Memory: 168KB
67 Submit time: 2016-11-18 20:26:05
68 ****************************************************/