NYOJ 20 吝啬的国度

吝啬的国度

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

难度：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

很明显，这个些城市和道路构成了一个极小连通子图，也就是生成树。而出发的城市S就相当于这棵树的树根，一种较易想到的解法就是从出发城市开始，对整个地图进行深度搜索，过程中记录下前一个城市的编号，如下，采用邻接表存储地图：

#include <stdio.h>

struct node
{
	int num;
	node *next;
};

struct data_type
{
	int priorCity;
	node *linkedCity;
}map[100005];

void MyDelete(int cityNum)
{
	int i;
	node *p, *q;
	for (i = 1; i <= cityNum; i++)
	{
		p = map[i].linkedCity;
		while (p != NULL)
		{
			q = p->next;
			delete p;
			p = q;
		}
	}
}

void Travel(int currentCity, int priorCity)
{
	map[currentCity].priorCity = priorCity;
	node *linkedCity = map[currentCity].linkedCity;
	while (linkedCity != NULL)
	{
		if (map[linkedCity->num].priorCity == 0)
		{
			Travel(linkedCity->num, currentCity);
		}
		linkedCity = linkedCity->next;
	}
}

int main()
{
	int i, testNum, cityNum, startCity, cityA, cityB;
	node *p;
	scanf("%d", &testNum);
	while (testNum-- != 0)
	{
		scanf("%d%d", &cityNum, &startCity);
		for (i = 0; i <= cityNum; i++)
		{
			map[i].priorCity = 0;
			map[i].linkedCity = NULL;
		}
		for (i = 1; i < cityNum; i++)
		{
			scanf("%d%d", &cityA, &cityB);
			p = new node;
			p->num = cityB;
			p->next = map[cityA].linkedCity;
			map[cityA].linkedCity = p;
			p = new node;
			p->num = cityA;
			p->next = map[cityB].linkedCity;
			map[cityB].linkedCity = p;
		}
		Travel(startCity, -1);
		for (i = 1; i < cityNum; i++)
		{
			printf("%d ", map[i].priorCity);
		}
		printf("%d\n", map[i].priorCity);
		MyDelete(cityNum);
	}
	return 0;
}

上面的地图相当于一个无向图，而在深度搜索时，需要的只是一个以出发城市为中心，向四周辐射的有向图。改进算法是在输入数据的同时，就进行搜索地图，因为数据输入未完成，所以输入时得到的是一个子图，这个子图分两种情况，一种是子图中包含出发城市，子图是一个有向图，所以可以根据输入的两个城市哪一个离出发城市更近，确定结果；另一种子图中不包含出发城市，此时，无法确定哪个城市离出发城市更近，所以先用邻接表将这个无向子图存储起来，等到它与出发城市相连时，在对这个子图进行深度搜索。

例如输入的测试数据为：

10 1

8 10

10 3

3 7

10 4

1 9

1 8

8 6

1 2

9 5

则首先得到一个不包含出发城市的子图：

在输入数据1 8时之后，上面的子图与出发城市相连，图中红色方块代表出发城市，虚线箭头代表并未在邻接表中建立此联系：

#include <stdio.h>

struct node
{
	int num;
	node *next;
};

struct data_type
{
	int priorCity;
	bool start;
	node *linkedCity;
}map[100005];

void InitMap(int cityNum, int startCity)
{
	int i;
	for (i = 0; i <= cityNum; i++)
	{
		map[i].priorCity = 0;
		map[i].start = false;
		map[i].linkedCity = NULL;
	}
	map[startCity].start = true;
	map[startCity].priorCity = -1;
}

void MyDelete(int cityNum)
{
	int i;
	node *p, *q;
	for (i = 1; i <= cityNum; i++)
	{
		p = map[i].linkedCity;
		while (p != NULL)
		{
			q = p->next;
			delete p;
			p = q;
		}
	}
}

void Travel(int currentCity, int priorCity)
{
	map[currentCity].priorCity = priorCity;
	map[currentCity].start = true;
	node *linkedCity = map[currentCity].linkedCity;
	while (linkedCity != NULL)
	{
		if (map[linkedCity->num].priorCity == 0)
		{
			Travel(linkedCity->num, currentCity);
		}
		linkedCity = linkedCity->next;
	}
}

int main()
{
	int i, testNum, cityNum, startCity, cityA, cityB;
	node *p;
	scanf("%d", &testNum);
	while (testNum-- != 0)
	{
		scanf("%d%d", &cityNum, &startCity);
		InitMap(cityNum, startCity);
		for (i = 1; i < cityNum; i++)
		{
			scanf("%d%d", &cityA, &cityB);
			if (map[cityA].start)
			{
				if (map[cityB].linkedCity != NULL)
				{
					Travel(cityB, cityA);
				}
				else
				{
					map[cityB].priorCity = cityA;
					map[cityB].start = true;
				}
			}
			else if (map[cityB].start)
			{
				
				if (map[cityA].linkedCity != NULL)
				{
					Travel(cityA, cityB);
				}
				else
				{
					map[cityA].priorCity = cityB;
					map[cityA].start = true;
				}
			}
			else
			{
				p = new node;
				p->num = cityB;
				p->next = map[cityA].linkedCity;
				map[cityA].linkedCity = p;
				p = new node;
				p->num = cityA;
				p->next = map[cityB].linkedCity;
				map[cityB].linkedCity = p;
			}
		}
		for (i = 1; i < cityNum; i++)
		{
			printf("%d ", map[i].priorCity);
		}
		printf("%d\n", map[i].priorCity);
		MyDelete(cityNum);
	}
	return 0;
}

深度搜索时采用非递归函数：

struct
{
	int currentNum;
	int priorNum;
}stack[100005], *base = NULL, *top = NULL;

void Travel(int currentCity, int priorCity)
{
	node *linkedCity = NULL;
	base = top = stack;
	top->currentNum = currentCity;
	top->priorNum = priorCity;
	top++;
	while (base != top)
	{
		currentCity = (--top)->currentNum;
		priorCity = top->priorNum;
		map[currentCity].priorCity = priorCity;
		map[currentCity].start = true;
		linkedCity = map[currentCity].linkedCity;
		while (linkedCity != NULL)
		{
			if (map[linkedCity->num].priorCity == 0)
			{
				top->currentNum = linkedCity->num;
				top->priorNum = currentCity;
				top++;
			}
			linkedCity = linkedCity->next;
		}
	}
}