欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NYOJ 20 吝啬的国度

程序员文章站 2022-07-15 16:04:18
...

吝啬的国度

时间限制: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 则首先得到一个不包含出发城市的子图:NYOJ 20 吝啬的国度

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

NYOJ 20 吝啬的国度

#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;
		}
	}
}