中文题面，给出一个图，问能不能成环，如果可以就输出YES。否则输出该树的直径。
这里的判环我们用路径压缩的并查集就能很快的判断出来，可以在输入的同时进行判断。这题重点就是求树的直径。
树直径的性质可以参考https://blog.csdn.net/pi9nc/article/details/12394117 实现在代码求法上的就是：
假设 s-t这条路径为树的直径，或者称为树上的最长路
从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路
搜的时候要注意 ，什么时候该清空什么数组 在代码中有一定的解释
#include<iostream> #include<vector> #include<queue> #include<string.h> using namespace std; #define p pair<int,int> vector<p> a[100050]; bool pd[100050],pdd[100050]; //pd数组判断该点有没有遍历到 pdd数组是保证每一个点都要被遍历过 int dp[100050]; //dp值为以改点为起点最长路径，在第一次找端点遍历后要清零 int ans,mark,anss;//annss为最终答案，mark用来标记第一次bfs找到的树的直径的端点 int bfs(int u) { ans=0; memset(pd,false,sizeof(pd)); memset(dp,false,sizeof(dp)); pd[u]=pdd[u]=1; queue<int> q; q.push(u); while(q.size()!=0) { int t=q.front(); q.pop(); for(int i=0;i<a[t].size();i++) { int v=a[t][i].first; if(pd[v]) continue; int w=a[t][i].second; //cout<<"w="<<w<<endl; pd[v]=pdd[v]=1; dp[v]=dp[t]+w; if(ans<dp[v]) { ans=dp[v]; mark=v; } q.push(v); } } return mark; } int f[100010];//压缩路径并查集 int die(int u) { if(f[u]==u) return u; f[u]=die(f[u]); return f[u]; } int main() { int i,j,k,l,x,y,n,huan,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(pdd,false,sizeof(pdd)); huan=0;anss=0; int u,v,c; for(i=1;i<=n;i++) f[i]=i,a[i].clear();//初始化father数组，同时清空上个输入留下的关系路径 for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&c); x=die(u);y=die(v); if(x!=y) f[x]=y; else huan=1; //代表能成环 a[u].push_back(p(v,c)); a[v].push_back(p(u,c)); } if(huan) { printf("YES "); continue; } for(i=1;i<=n;i++) //循环保证所有的点都被遍历过 { if(!pdd[i]) { int sb=bfs(i); // cout<<ans<<endl; // cout<<"sb="<<sb<<endl; int hp=bfs(sb); // cout<<ans<<endl; anss=max(anss,dp[hp]); } } printf("%d ",anss); } }