图的深度优先搜索(邻接表)

本文主要是介绍图的深度优先搜索(邻接表)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

给出图的顶点数和顶点与顶点之间的连接关系，请输出用邻接表存储的图的深度优先搜索顶点序列。

Input

输入的第一行是一个整数T表示测试示例的数目，每组示例的第一行有两个数m(2<=m<=10)和n(1<=n<=m*(m-1)/2)，m表示顶点的个数(顶点的标号从1-m)，n表示边的个数。下面n行的每行表示一条边。后面一行是一个数k，k表示需要搜索的顶点数量。后面k行每行有一个数表示从该顶点开始搜索。在搜索过程中与同一个顶点相邻的顶点按存储的先后顺序进行搜索。

Output

每组输出k行，每行为从输入的一个顶点开始搜索的深度优先搜索序列。每组搜素结果之间用空行隔开。

Sample Input

Sample Output

1 2
2 1

//标程：#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
int n,m,vis[15],cnt;
vector<int> v[15];
void dfs(int x)
{
cnt++;
	if(cnt<m) printf("%d ",x);
	if(cnt==m) printf("%d\n",x);
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i] && !vis[v[x][i]])
		{
			vis[v[x][i]]=1;
			dfs(v[x][i]);
		}
	}
}
int main()
{
	//freopen("a.txt","r",stdin);
int t,i,k,a,b,x;
	scanf("%d",&t);
while(t--)
	{
		scanf("%d%d",&m,&n);
		for(i=1;i<=m;i++) 
			v[i].clear();
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&a,&b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		scanf("%d",&k);
		for(i=1;i<=k;i++)
		{
			scanf("%d",&x);
			memset(vis,0,sizeof(vis));
			cnt=0;
			vis[x]=1;
			dfs(x);
		}
		if(t!=0) printf("\n"); 
	}
	return 0;
}