题意:(略) 注意求的长度是指树中最长的链,即树的直径 注意这里可能是不连通图
先 dfs 判断图中是否有环,然后求树的直径,做法是 以任意一点u,为根节点,dfs找到最远的点 start,再以该节点为根节点 dfs,找到的最远的点,它们的距离就是解。
code:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cassert> #include <cstring> #include <string> #include <iomanip> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #define LL long long #define inf 0x3f3f3f3f #define eps 1e-9 #define PA system("pause") #define PI acos(-1.0) using namespace std; #define M 100005 int vis[M],head[M],dis[M]; struct edge { int to, w, next; }e[2000005]; int ecnt, n, st; void addedge(int u, int v, int w) { e[ecnt].to = v; e[ecnt].w = w; e[ecnt].next = head[u]; head[u] = ecnt++; } void dfs1(int u) //从u 出发找最远的点 { vis[u] = 1; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; if(!vis[v]) { dis[v] = dis[u] + e[i].w; dfs1(v); } } } int dfs(int u,int fa) // dfs判断有没有环 { vis[u] = 1; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; if(v != fa){ if(vis[v]) return 1; if(dfs(v, u)) return 1; } } return 0; } bool check() { for(int i = 1; i <= n; i++) { if(!vis[i]) { if(dfs(i, -1)) return 1; } } return 0; } int getdia(int u) //找树的直径 { int i; for(i = 1; i <= n; i++) dis[i] = (i==u? 0:inf); dfs1(u); int len = -1; for(i = 1; i <= n; i++) { if(dis[i] != inf && dis[i] > len) { len = dis[i]; st = i; } } for(i = 1; i <= n; i++) dis[i] = (i==st? 0:inf); memset(vis, 0, sizeof(vis)); dfs1(st); len = -1; for(i = 1; i <= n; i++) { if(dis[i] != inf && dis[i] > len) len = dis[i]; } return len; } int main() { int m, x, y, z; while(scanf("%d%d",&n,&m) != EOF) { memset(head, -1, sizeof(head)); ecnt = 0; while(m--) { scanf("%d%d%d",&x,&y,&z); addedge(x, y, z); addedge(y, x, z); } memset(vis,0,sizeof(vis)); if(check()) puts("YES"); else { memset(vis, 0 ,sizeof(vis)); int ans = -1; for(int i = 1; i <= n; i++) { if(!vis[i]) { ans = max(ans, getdia(i)); } } printf("%d\n",ans); } } return 0; }