类似于树的直径,从随意一个点出发,找到距离该点最远的且度数最少的点.

然后再做一次最短路

Friend Chains

3
XXX
YYY
ZZZ
2
XXX YYY
YYY ZZZ
0

2

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月17日 星期一 16时35分00秒
File Name     :HDOJ4460.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=2100;

int n,m;
int id=1;
map<string,int> msi;


int getID(string name)
{
	if(msi[name]==0) msi[name]=id++;
	return msi[name]; 
}

struct Edge
{
	int to,next,cost;
}edge[maxn*maxn];

int Adj[maxn],Size;
int du[maxn];

void init()
{
	id=1; msi.clear();
	memset(du,0,sizeof(du));
	memset(Adj,-1,sizeof(Adj)); Size=0;
}

void Add_Edge(int u,int v)
{
	edge[Size].to=v;
	edge[Size].cost=1;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}

int dist[maxn],cq[maxn];
bool inq[maxn];

bool spfa(int st)
{
    memset(dist,63,sizeof(dist));
    memset(cq,0,sizeof(cq));
    memset(inq,false,sizeof(inq));
    dist[st]=0;
    queue<int> q;
    inq[st]=true;q.push(st); cq[st]=1;

    while(!q.empty())
    {
        int u=q.front();q.pop();

        for(int i=Adj[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dist[v]>dist[u]+edge[i].cost)
            {
                dist[v]=dist[u]+edge[i].cost;
                if(!inq[v])
                {
                    inq[v]=true;
                    cq[v]++;
                    if(cq[v]>=n+10) return false;
                    q.push(v);
                }
            }
        }
        inq[u]=false;
    }
    return true;
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	while(scanf("%d",&n)!=EOF&&n)
	{
		init();
		string name1,name2;
		for(int i=1;i<=n;i++) 
		{
			cin>>name1;
		}
		scanf("%d",&m);
		for(int i=0;i<m;i++)
		{
			cin>>name1>>name2;
			int id1=getID(name1);
			int id2=getID(name2);
			Add_Edge(id1,id2); Add_Edge(id2,id1);
			du[id1]++; du[id2]++;
		}
		spfa(1);
		int st=1;
		for(int i=2;i<=n;i++)
		{
			if(dist[st]<dist[i]) st=i;
			else if(dist[st]==dist[i])
			{
				if(du[st]>du[i]) st=i;
			}
		}
		spfa(st);
		int ans=0;
		for(int i=1;i<=n;i++) ans=max(ans,dist[i]);
		if(ans==INF) ans=-1;
		cout<<ans<<endl;
	}
    
    return 0;
}