Timus 1837. Isenbaev's Number 图论 题解

Vladislav Isenbaev is a two-time champion of Ural, vice champion of TopCoder Open 2009, and absolute champion of ACM ICPC 2009. In the time you will spend reading this problem statement Vladislav would have solved a problem. Maybe, even two…

Since Vladislav Isenbaev graduated from the Specialized Educational and Scientific Center at Ural State University, many of the former and present contestants at USU have known him for quite a few years. Some of them are proud to say that they either played in the same team with him or played in the same team with one of his teammates…

Let us defineIsenbaev's numberas follows. This number for Vladislav himself is 0. For people who played in the same team with him, the number is 1. For people who weren't his teammates but played in the same team with one or more of his teammates, the number is 2, and so on. Your task is to automate the process of calculating Isenbaev's numbers so that each contestant at USU would know their proximity to the ACM ICPC champion.

Input

The first line contains the number of teamsn(1 ≤n≤ 100). In each of the followingnlines you are given the names of the three members of the corresponding team. The names are separated with a space. Each name is a nonempty line consisting of English letters, and its length is at most 20 symbols. The first letter of a name is capital and the other letters are lowercase.

Output

For each contestant mentioned in the input data output a line with their name and Isenbaev's number. If the number is undefined, output “undefined” instead of it. The contestants must be ordered lexicographically.

Sample

input output

7 Isenbaev Oparin Toropov Ayzenshteyn Oparin Samsonov Ayzenshteyn Chevdar Samsonov Fominykh Isenbaev Oparin Dublennykh Fominykh Ivankov Burmistrov Dublennykh Kurpilyanskiy Cormen Leiserson Rivest	Ayzenshteyn 2 Burmistrov 3 Chevdar 3 Cormen undefined Dublennykh 2 Fominykh 1 Isenbaev 0 Ivankov 2 Kurpilyanskiy 3 Leiserson undefined Oparin 1 Rivest undefined Samsonov 2 Toropov 1

本题属于图论的应用了。

有两个思路：

1 Dijstra求一点都其他所有点的最短路径

2 宽度优先的图搜索

两者的时间效率和空间效率都是一样的。

难度指数看情况而定吧。有人说很简单。

但是对于对图论不太熟悉的人来说就一点都不简单了。

尤其是使用C++来实现更加难，因为要操作繁琐的指针问题。

本人对图论也不够熟，所以本题对我来说还是挺有难度的。做熟了LeetCode题目，但是LeetCode题好像只有一题是牵涉图论的，还是复制图问题，相当于遍历问题了。

我这里使用第二个思路来做：

1 读入数据，同时构造一个邻接矩阵

注意： a） 使用一个map来检测是否是重复的名字了，如果是重复的那么就不需要构造新的节点了，而是从map中取出之前的节点处理

b）使用int n代表距离，其中n初始化为-1，代表没有访问过的节点，并可以根据这个值来防止重复访问图中的节点，避免无限循环

c） 巧用set来避免重复节点，减少多余的访问

d）注意使用指针，不使用指针的话就不能保证数据的单一性，可能会在操作副本也说不定，那么结果很容易出错 -- 我就载在这里了。这就是为什么C++那么难，那么多人都谈指针色变啊！所以一定要熟练地使用指针，使用容器如vector和set来装载指针操作，否则就成了操作副本了。

2 使用Isenbaev来初始化根节点，进行宽度优先遍历图，注意可以没有Isenbaev这个节点（好像很多人载在这里），那么就可以提前结束循环了。注意判断节点是否遍历过了，判断其距离是否是-1，-1代表没访问过。

3 技巧：使用set容器装载所有数据，就已经自动排序好了，那么可以直接打印出来，而不需要排序了。这些数据就是之前装载在map中的数据。而没必要去遍历图

最后时间效率和空间效率都是O(n)了，还是挺高效的。

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
using namespace std;

static const string NAME = "Isenbaev";

//使用邻接矩阵图来做本题
struct IsenStrAdj
{
	int n;
	string name;
	vector<IsenStrAdj *> nexts;
	IsenStrAdj(string name1 = "", int n1 = -1):n(n1), name(name1), nexts(){}
	bool operator<(const IsenStrAdj &isen) const
	{
		return name < isen.name;
	}
};

class IsenAjecentAlgo
{
public:
	void run()
	{
		int n = 0;
		cin>>n;
		unordered_map<string, IsenStrAdj *> umpSi;
		string tmpName;
		for (int i = 0; i < n; i++)
		{
			vector<IsenStrAdj *> vis;
			for (int j = 0; j < 3; j++)
			{
				cin>>tmpName;
				IsenStrAdj *isen = nullptr;
				if (umpSi.count(tmpName)) isen = umpSi[tmpName];
				else
				{
					isen = new IsenStrAdj(tmpName);
					umpSi[tmpName] = isen;
				}
				vis.push_back(isen);				
			}
			
			for (int k = 0; k < 3; k++)
			{
				IsenStrAdj *isen = vis[k];
				set<IsenStrAdj *> sis(isen->nexts.begin(),isen->nexts.end());
				for (int j = 0; j < 3; j++)
				{
					if (isen != vis[j])
					{
						IsenStrAdj *t = vis[j];
						sis.insert(t);
					}
				}
				isen->nexts.assign(sis.begin(), sis.end());//确保无重复
			}
		}
		IsenStrAdj *isen = umpSi.count(NAME)? umpSi[NAME] : nullptr;
		numberThem(isen);

		set<IsenStrAdj> setIsen;
		for (auto x:umpSi)
		{
			setIsen.insert(*(x.second));
		}
		for (auto x:setIsen)
		{
			cout<<x.name<<' ';
			if (-1 == x.n) cout<<"undefined"<<endl;
			else cout<<x.n<<endl;
		}
	}

	void numberThem(IsenStrAdj *isen)
	{
		if (!isen) return ;
		queue<IsenStrAdj *> qu;
		qu.push(isen);
		isen->n = 0;
		int lv = 0;
		while (qu.size())
		{
			lv++;
			queue<IsenStrAdj *> lv_next;
			while (qu.size())
			{
				isen = qu.front();
				qu.pop();
				for (int i = 0; i < isen->nexts.size(); i++)
				{
					if (-1 != isen->nexts[i]->n) continue;
					IsenStrAdj *t = (isen->nexts[i]);
					t->n = lv;
					lv_next.push(t);
				}
			}
			qu = lv_next;
		}
	}
};

int main()
{
	IsenAjecentAlgo isen;
	isen.run();
	return 0;
}