[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int> g[100010];
int dis[100010];
int dfs(int s)
{
memset(dis,-1,sizeof dis);
vector<int> stk;
stk.push_back(s);
dis=0;
int farthest=s;
while(!stk.empty())
{
int now=stk.back();
stk.pop_back();
for(int i=0;i<g[now].size();i++)
if(dis[g[now]]==-1)
{
dis[g[now]]=dis[now]+1;
stk.push_back(g[now]);
if(dis[g[now]]>dis[farthest])
farthest=g[now];
}
}
return farthest;
}
int main()
{
ios::sync_with_stdio(0);
int n,m;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
g.clear();
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g.push_back(a);
}
int a=dfs(0);
int b=dfs(a);
cout<<dis<<endl;
}
}
[C++] 純文本查看 復制代碼
#include <cstdio> //c¿é¤J¿é¥X
#include <iostream>
using namespace std;
struct V{
int a;
int b;
bool x;
};
V v1[100001],v2[100001];
int main(){
int n,m;
while(~scanf("%d",&n)){
scanf("%d",&m);
for(int q=0;q<m;q++){
scanf("%d%d",&v1[q].a,&v1[q].b);
v1[q].x=0;
v2[q].a=v1[q].a;
v2[q].b=v1[q].b;
v2[q].x=0;
}
int tree[n];
for(int q=0;q<n;q++)tree[q]=-1;
tree[v1[0].a]=0;
tree[v1[0].b]=1;
v1[0].x=1;
bool empty=1;
while(empty){
empty=0;
for(int q=0;q<m;q++){
if(v1[q].x==0&&tree[v1[q].a]!=-1){
tree[v1[q].b]=tree[v1[q].a]+1;
v1[q].x=1;
empty=1;
}
else if(v1[q].x==0&&tree[v1[q].b]!=-1){
tree[v1[q].a]=tree[v1[q].b]+1;
v1[q].x=1;
empty=1;
}
}
}
int maxd=-1,maxn=-1;
for(int q=0;q<n;q++){
if(tree[q]>maxd){
maxd=tree[q];
maxn=q;
}
tree[q]=-1;
}
tree[maxn]=0;
empty=1;
while(empty){
empty=0;
for(int q=0;q<m;q++){
if(v2[q].x==0&&tree[v2[q].a]!=-1){
tree[v2[q].b]=tree[v2[q].a]+1;
v2[q].x=1;
empty=1;
}
else if(v2[q].x==0&&tree[v2[q].b]!=-1){
tree[v2[q].a]=tree[v2[q].b]+1;
v2[q].x=1;
empty=1;
}
}
}
// for(int q=0;q<n;q++)cout<<tree[q]<<" ";
maxd=-1,maxn=-1;
for(int q=0;q<n;q++){
if(tree[q]>maxd){
maxd=tree[q];
maxn=q;
}
}
printf("%d\n",maxd);
}
}