nyoj题目20吝啬的国度【深搜】

吝啬的国度

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

描述

在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

输入

第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1）

样例输入

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

样例输出

-1 1 10 10 9 8 3 1 1 8

//vector< vector<int> >map代替邻接矩阵
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int mark[100001],end[100001],num,n,qi,a,b;
vector< vector<int> >map(100001);
void dfs(int v)
{
	int i;
	mark[v]=1;
	end[v]= num;
	for(i=0;i<map[v].size();i++)
	{
		if(mark[map[v][i]]==0)
		{
			num = v;
			dfs(map[v][i]);
		}
	}
}
int main()
{
	int T,j,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&qi);
		for(i=0;i<=n;i++)
		mark[i]=0;
		for(i=0;i<=n;i++)
			map[i].clear();
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			map[a].push_back(b);
			map[b].push_back(a);
		}
		num=-1;
		dfs(qi);
		for(i=1;i<n;i++)
			printf("%d ",end[i]);
		printf("%d\n",end[i]);
	}
	return 0;
} 

// 学长典型代码
#include <stdio.h>
#include <string.h>
int map[100005];
void Adjust(int a)
{
	int s=map[a];
	if(s)
	{
		Adjust(s);
		map[s]=a;
	}
}
int main()
{
	int m,n,s,i,a,b;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d",&n,&s);
		memset(map,0,sizeof(int)*n+1);
		for(i=1; i<n; i++)
		{
			scanf("%d%d",&a,&b);
			if(!map[b])
				map[b]=a;
			else
			{
				Adjust(a);
				map[a]=b;
			}
		}
		Adjust(s);
		map[s]=-1;
		for(i=1; i<=n; i++)
			printf(i<n?"%d ":"%d\n",map[i]);
	}
	return 0;
}

// 周文坤邻接矩阵代码
#include<stdio.h>
struct Node
{
	int next;
	Node *link;
}v[100001];
int vert,source,num;
int res[100001];
void  DFS(int source)
{
	res[source] = num;
	for(Node *node = v[source].link;node;node = node->link)
	{
		num = source;
		if(!res[node->next])
		DFS(node->next);
	}
}
void Init()
{
	for(int i=0;i<=vert;i++)
	{
		v[i].next = i;
		res[i] = 0;
		v[i].link = NULL;
	}
}
int main()
{
	int n,vert,source,s,e;
	int i,j,k;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&vert,&source);
		for(int i=0;i<=vert;i++)
		{
			v[i].next = i;
			res[i] = 0;
			v[i].link = NULL;
		}
		for(i=1;i<vert;i++)
		{
			scanf("%d%d",&s,&e);
			Node *node = new Node;
			node->next = e;
			node->link = v[s].link;
			v[s].link = node;
			Node *node1 = new Node;
			node1->next = s;
			node1->link = v[e].link;
			v[e].link = node1;
		}
		num = -1;
		DFS(source);
		res[source] = -1;
		printf("%d",res[1]);
		for(i=2;i<=vert;i++)
		{
			printf(" %d",res[i]);
		}
		printf("\n");
	}
	return 0;
}