首页 > 代码库 > HDU 4460
HDU 4460
题意:问给定的一张图中,相距最远的两个点的距离为多少。
解法:跟求树的直径差不多,从1 开始bfs,得到一个最远的点,然后再从该点bfs一遍,得到的最长距离即为答案。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <queue>#include <map>using namespace std;#define N 100007map<string,int> mp;vector<int> G[1006];int vis[1006],n,m,Maxdis,Maxtag;struct node{ int dis,u;};void dfs(int u){ vis[u] = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!vis[v]) dfs(v); }}void bfs(int u){ queue<node> que; memset(vis,0,sizeof(vis)); node now; now.dis = 0; now.u = u; que.push(now); vis[u] = 1; while(!que.empty()) { int SZ = que.size(); while(SZ--) { node tmp = que.front(); que.pop(); int dis = tmp.dis; int u = tmp.u; if(dis > Maxdis) { Maxdis = dis; Maxtag = u; } for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!vis[v]) { now.u = v; now.dis = dis+1; vis[v] = 1; que.push(now); } } } }}int main(){ int i,j; string S; while(scanf("%d",&n)!=EOF && n) { mp.clear(); for(i=1;i<=n;i++) { cin>>S; mp[S] = i; G[i].clear(); } scanf("%d",&m); string A,B; for(i=1;i<=m;i++) { cin>>A>>B; int a = mp[A], b = mp[B]; G[a].push_back(b); G[b].push_back(a); } memset(vis,0,sizeof(vis)); dfs(1); int Link = 1; for(i=1;i<=n;i++) if(!vis[i]) Link = 0; if(!Link) { puts("-1"); continue; } Maxdis = 0, Maxtag = -1; bfs(1); int S = Maxtag; Maxdis = 0, Maxtag = -1; bfs(S); printf("%d\n",Maxdis); } return 0;}
HDU 4460
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。