题目链接：https://vjudge.net/problem/HDU-4460
题目大意：给你n个点让你找任意两个点之间最大距离的最小值
用bfs对每个点做起点的情况做一次搜索，找出其中的最大值
#include<set> #include<map> #include<stack> #include<queue> #include<cmath> #include<cstdio> #include<cctype> #include<string> #include<vector> #include<climits> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define endl '\n' #define rtl rt<<1 #define rtr rt<<1|1 #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define maxx(a, b) (a > b ? a : b) #define minn(a, b) (a < b ? a : b) #define zero(a) memset(a, 0, sizeof(a)) #define INF(a) memset(a, 0x3f, sizeof(a)) #define IOS ios::sync_with_stdio(false) #define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n") using namespace std; typedef long long ll; typedef pair<int, int> P; typedef pair<ll, ll> P2; const double pi = acos(-1.0); const double eps = 1e-7; const ll MOD = 1000000007LL; const int INF = 0x3f3f3f3f; const int _NAN = -0x3f3f3f3f; const double EULC = 0.5772156649015328; const int NIL = -1; template<typename T> void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } const int maxn = 1e3+10; map<string, int> mark; vector<int> edge[maxn]; int vis[maxn]; // int bfs(int stt) { // zero(vis); // int ans = 0; // queue<P> qe; // qe.emplace(0, stt); // while(!qe.empty()) { // P t = qe.front(); // int u = t.second; // qe.pop(); // if (vis[u]) continue; // // vis[u] = true; //标记的地方不一样速度差了3倍 // ans = max(ans, t.first); // ++t.first; // for (auto v : edge[u]) // if (!vis[v]) // qe.emplace(t.first, v); // } // return ans; // } int bfs(int stt) { zero(vis); int ans = 0; queue<P> qe; vis[stt] = true; qe.emplace(0, stt); while(!qe.empty()) { P t = qe.front(); int u = t.second; qe.pop(); ans = max(ans, t.first); ++t.first; for (auto v : edge[u]) { if (vis[v]) continue; vis[v] = true; qe.emplace(t.first, v); } } return ans; } int main(void) { IOS; int n; while(cin >> n && n) { string s1, s2; for (int i = 0; i<n; ++i) { cin >> s2; mark[s2] = i+1; } int m; cin >> m; while(m--) { cin >> s1 >> s2; edge[mark[s1]].push_back(mark[s2]); edge[mark[s2]].push_back(mark[s1]); } int ans = 0; for (int i = 1; i<=n; ++i) { if (edge[i].empty()) { ans = -1; break; } ans = max(ans, bfs(i)); } cout << ans << endl; for (int i = 0; i<=n; ++i) edge[i].clear(); mark.clear(); } return 0; }