题目链接: hdu4460 ( Friend Chains )
将每个人当作顶点,朋友关系当作顶点之间权值为 \(1\) 的边,建立无向图。
图上任意两点间最短距离的最大值即为所求,从每个顶点 \(bfs\) 就最大距离即可,时间复杂度 \(O(n^2)\) 。
特别地,若该图不连通,则输出 \(-1\) 。
/**
* hdu4460 Friend Chains
*
*/
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <string>
#include <stack>
#include <vector>
#include <map>
using namespace std;
const int N = 1005;
vector<int> G[N];
bool vis[N];
int n, m;
struct node{int x, step;};
int bfs(int s)
{
memset(vis, 0, sizeof vis);
queue<node>Q;
Q.push(node{s, 0});
vis[s] = 1;
int ans = 0;
while (!Q.empty()) {
node t = Q.front(); Q.pop();
ans = max(ans, t.step);
for (int i = 0; i < G[t.x].size(); ++i) {
int y = G[t.x][i];
if (vis[y]) continue;
Q.push(node{y, t.step+1});
vis[y] = 1;
}
}
return ans;
}
int main()
{
while (cin >> n && n) {
string s;
int cnt = 0;
map<string, int> mp;
for (int i = 1; i <= n; ++i) cin >> s, mp[s] = ++cnt;
cin >> m;
memset(vis, 1, sizeof vis);
for (int i = 1; i <= n; ++i) G[i].clear();
for (int i = 0; i < m; ++i) {
string a, b;
cin >> a >> b;
int x = mp[a];
int y = mp[b];
G[x].push_back(y);
G[y].push_back(x);
vis[x] = vis[y] = 0;
}
bool flag = false;
for (int i = 1; i <= n; ++i) {
if (vis[i]) {
cout << "-1" << endl;
flag = true;
break;
}
}
if (flag) continue;
int ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, bfs(i));
cout << ans << endl;
}
return 0;
}