Friend Chains [hdu 4460]

*Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9896 Accepted Submission(s): 3069
*

Problem Description

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

题目大致解读：每组数据有 n 个顶点和 2m 条边(无向图)，要求寻找到点与点之间的最大距离。如果存在孤立点，即与其他点之间没有联系，则返回 -1

思路：

与最短路问题相似，边权为 1，但这题的要求是寻找最长路。已知边权都为一时求解最短路的一种方法为BFS 把所有边都遍历一遍，找到最短值，那么同样根据 BFS 不重不漏的特性，我们同样可以找到两个点之间的最长值。考虑到不同的起点出发最后的最长路是不同的，因此我们需要把每个点都 BFS 一遍

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 5, M = 2e4 + 5; // 点数，边数

int n, m;
map<string, int> name;
bool vis[N]; // 标记防止重复访问

int h[N], e[M], ne[M], idx; // 邻接表存图
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

// bfs 返回从起点出发的最远距离
int bfs(int start){
    queue<PII> q;
    memset(vis, 0, sizeof vis);
    vis[start] = true; // 标记已访问起点
    q.push({start, 0});

    int distance = 0;
    while(!q.empty()){
        auto t = q.front(); // t.first点号，t.second距离
        q.pop();
        distance = max(distance, t.second);

        for(int i = h[t.first]; i != -1; i = ne[i]){ // 访问下一个点
            int nxt = e[i]; // 下一个点的编号
            if(vis[nxt]) continue;
            vis[nxt] = true;
            q.push({nxt, t.second + 1});
        }
    }

    for(int i = 1; i <= n; i ++){ // 遍历vis数组，如有没被访问的点，则这个点为孤立点，返回-1
        if(!vis[i]) return -1;
    }
    return distance; // 返回最大距离
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    while(cin >> n && n != 0){
        name.clear();
        for(int i = 1; i <= n; i ++){
            cin >> s;
            name[s] = i; // 姓名编号映射
        }

        cin >> m;
        memset(h, -1, sizeof h);
        idx = 0;
        string s1, s2;
        for(int i = 1; i <= m; i ++){
            cin >> s1 >> s2;
            add(name[s1], name[s2]);
            add(name[s2], name[s1]);
        }

        int res = 0;
        for(int i = 1; i <= n; i ++){
            int dis = bfs(i);
            if(dis == -1){
                res = -1;
                break;
            }
            else res = max(res, dis);
        }

        cout << res << '\n';
    }

    return 0;
}