题意：给定一个无向图，图可能是非连通的，如果图中存在环，就输出YES，否则就输出图中最长链的长度。
分析：首先我们得考虑这是一个无向图，而且有可能是非连通的，那么就不能直接像求树那样来求最长链。对于本题，首先得
判断环，在这里我们就用并查集判环，因为并查集本身就是树型结构，如果要连接的两点的祖先都相同，那么就已经有环了，
这样直接输出YES，如果没有环，就应该输出最长链长度，那么我们每次可以对每一个没有访问过的节点进行两次bfs，就可以
求出，然后每次更新最大值即可。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <queue> using namespace std; const int N=100005;
const int M=2000005; int pre[N],n,m,res;
int head[N],to[M],next[M],w[M],edge;
int tosum[N],dis[N],que[N];
bool vis[N],used[N];
queue <int>Q; void init()
{
edge=0;
memset(head,-1,sizeof(head));
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)
pre[i]=i;
} int find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
//路径压缩
int i=x,j;
while(i!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
} void Union(int x,int y)
{
int fx = find(x);
int fy = find(y);
if(fx!=fy) pre[fx]=fy;
} void add(int u,int v,int c)
{
to[edge]=v,w[edge]=c,next[edge]=head[u],head[u]=edge++;
to[edge]=u,w[edge]=c,next[edge]=head[v],head[v]=edge++;
} void bfs(int s)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[s]=1; dis[s]=0;
while(!Q.empty()) Q.pop();
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
used[u]=1;
for(int i=head[u]; ~i; i=next[i])
{
int v=to[i];
if(!vis[v])
{
vis[v]=1;
dis[v]=dis[u]+w[i];
Q.push(v);
}
}
}
} int treediameter(int s)
{
int u,maxl;
bfs(s);
maxl=0,u=s;
for(int i=1; i<=n; i++)
if(dis[i]>maxl)
u=i,maxl=dis[i];
bfs(u);
maxl=0;
for(int i=1; i<=n; i++)
if(dis[i]>maxl)
maxl=dis[i];
return maxl;
} int main()
{
int u,v,d,i;
while(~scanf("%d%d",&n,&m))
{
init();
bool f=0;
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(find(u)==find(v)) f=1;
Union(u,v);
add(u,v,d);
}
if(f) puts("YES");
else
{
res=-1;
for(i=1;i<=n;i++)
if(!used[i]) res=max(res,treediameter(i));
printf("%d\n",res);
}
}
return 0;
}