首页 > 代码库 > 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;}
View Code

 

HDU 4460