树的直径
并查集判环,SPFA判环一直T。。。。(写的太挫了估计。。。)
#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <queue> using namespace std; int const MAXN = 100010; typedef struct EDGE{ int to; int w; }Edge; vector <Edge> edge[MAXN]; queue <int> q; int cnt[MAXN],vis[MAXN],dis[MAXN]; int father[MAXN]; int n,m; void Init(){ for(int i = 0;i < MAXN;i++){ father[i] = i; edge[i].clear(); } } void Add(int u,int v,int w){ Edge temp; temp.w = w; temp.to = v; edge[u].push_back(temp); temp.to = u; edge[v].push_back(temp); } int Find(int x){ int temp,y; y = x; while(y != father[y]){ y = father[y]; } while(x != father[x]){ temp = father[x]; father[x] = y; x = temp; } return y; } void Union(int u,int v){ int uu = Find(u); int vv = Find(v); if(uu != vv) father[uu] = vv; } void Bfs(int start){ while(!q.empty()){q.pop();}; memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); vis[start] = 1; dis[start] = 0; q.push(start); while(!q.empty()){ int top = q.front(); q.pop(); for(int i = 0;i < edge[top].size();i++){ int to = edge[top][i].to; if(!vis[to]){ vis[to] = 1; dis[to] = dis[top] + edge[top][i].w; q.push(to); } } } } int Count(int start){ int u = start, maxx = 0; Bfs(u); for(int i = 1;i <= n;i++){ if(dis[i] > maxx){ u = i; maxx = dis[i]; } } Bfs(u); maxx = 0; for(int i = 1;i <= n;i++){ if(dis[i] > maxx) maxx = dis[i]; } return maxx; } int main(){ while(~scanf("%d%d",&n,&m)){ Init(); int u,v,w,flag = 0; for(int i = 0;i < m;i++){ scanf("%d%d%d",&u,&v,&w); Add(u,v,w); if(Find(u) == Find(v)) flag = 1; Union(u,v); } if(flag) printf("YES\n"); else{ printf("%d\n",Count(u)); } } return 0; }