【 HDU - 4460 】 G - Friend Chains (BFS)

For a group of people, there is an idea that everyone is equals to or less than 6 steps away from any other person in the group, by way of introduction. So that a chain of “a friend of a friend” can be made to connect any 2 persons and it contains no more than 7 persons.
For example, if XXX is YYY’s friend and YYY is ZZZ’s friend, but XXX is not ZZZ’s friend, then there is a friend chain of length 2 between XXX and ZZZ. The length of a friend chain is one less than the number of persons in the chain.
Note that if XXX is YYY’s friend, then YYY is XXX’s friend. Give the group of people and the friend relationship between them. You want to know the minimum value k, which for any two persons in the group, there is a friend chain connecting them and the chain’s length is no more than k .

Input

There are multiple cases.
For each case, there is an integer N (2<= N <= 1000) which represents the number of people in the group.
Each of the next N lines contains a string which represents the name of one people. The string consists of alphabet letters and the length of it is no more than 10.
Then there is a number M (0<= M <= 10000) which represents the number of friend relationships in the group.
Each of the next M lines contains two names which are separated by a space ,and they are friends.
Input ends with N = 0.

Output

For each case, print the minimum value k in one line.
If the value of k is infinite, then print -1 instead.

Sample Input

3
XXX
YYY
ZZZ
2
XXX YYY
YYY ZZZ
0

Sample Output

2

---

思路：

要找到相聚最远两个朋友的距离，因为不确定哪两个点最远（可能是直线，也可能是环，还可能不连通），所以跑一遍BFS找到最远的（写题解的时候突然想到，貌似应该也可以用 树的直径做这题，只用跑两次），

---

代码：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
const int maxn=1050;
int n,m;
vector<int> g[maxn];

int bfs(int s)
{
	    int num=0,sp[maxn],ans=0; //num计数判断是否连通，sp记录距离
		bool inq[maxn]={false};  //是否入队
		queue<int> q;
		q.push(s);
		sp[s]=0;
		inq[s]=1;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			ans=max(ans,sp[u]);
			num++;
			for(int i=0;i<g[u].size();i++)
			{
				int v=g[u][i];
				if(!inq[v])
				{
					inq[v]=1;
					sp[v]=sp[u]+1;
					q.push(v);
				}
			}
		}
		if(num==n) return ans;  //连通，返回最远距离
		else return -1;  //不连通
}


int main()
{
	while(cin>>n && n)
	{
		string name,name1;
		map<string,int> mp;  //名称-->编号
		
		for(int i=0;i<n;i++)
		{
			cin>>name;
			mp[name]=i;  //编号
		} 
			
		cin>>m;
		for(int i=0;i<m;i++)
		{
			cin>>name>>name1;
			g[mp[name]].push_back(mp[name1]); //无向图
			g[mp[name1]].push_back(mp[name]);
		}
		
		int fans=-1;  //记录最远距离
		for(int i=0;i<n;i++)  //跑一遍BFS
		{
			int z=bfs(i);
			if(z==-1)  //不连通直接输出-1，结束
			{
				cout<<-1<<endl;
				break;
			}
			else fans=max(fans,z);  //更新最远距离
		}
		if(fans!=-1) cout<<fans<<endl;  //判断条件应该可以去了
		
		for(int i=0;i<n;i++) g[i].clear(); //清空图（也可以放while下面）
	}
	return 0;
}