HDU 4460 Friend Chains

题目链接：HDU 4460展开目录

题解展开目录

给定 n 个人，和关系，问你这个朋友圈里任意两者之间最短的距离是多少。很明显的一个 BFS, 只要去找最长距离就好。如果不能全找到，就是 - 1。

代码展开目录

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std ;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1e3 + 5;
const int dr[] = {0, 0, -1, 1};
const int dc[] = {-1, 1, 0, 0};
int n, m;
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}
map<string, int> id;
vector<int> G[maxn];
int getid(const string &s){
    return id[s];
}
int vis[maxn];
int vvis[maxn];
int d[maxn];
 
int bfs(int rt){
    queue<int> q;
    q.push(rt);
    memset(vis, 0, sizeof(vis));
    memset(d, -1, sizeof(d));
    vis[rt] = vvis[rt] = 1;
    int ans = rt;
    d[rt] = 0;
    int mmax = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i];
            if(vis[v]) continue;
            vis[v] = vvis[v] = 1;
            d[v] = d[u] + 1;
            if(mmax < d[u] + 1){
                mmax = d[u] + 1;
                ans = v;
            }
            q.push(v);
        }
    }
    return ans;
}
 
int solve(int i){
    int u = bfs(i);
    int v = bfs(u);
    return d[v];
}
 
int main(){
    while(scanf("%d", &n) == 1 && n){
        id.clear();
        string s, s1, s2;
        for(int i = 1; i <= n; ++i){
            cin >> s;
            id[s] = i;
            G[i].clear();
        }
        scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            cin >> s1 >> s2;
            int u = getid(s1);
            int v = getid(s2);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if(m + 1 < n){  printf("-1\n"); continue; }
        memset(vvis, 0, sizeof(vvis));
        int ans = 0;
        for(int i = 1; i <= n; ++i)
            if(!vvis[i]) ans = max(ans, solve(i));
        for(int i = 1; i <= n; ++i)
            if(d[i] == -1){  ans = -1;  break; }
        printf("%d\n", ans);
    }
    return 0;
}