题目链接:Click here~~
题意:
给一个无向图,若有环输出YES,若无环,则是森林,输出 max { 树的直径 }。(树中最长的简单路)
解题思路:
早早地就搜了几篇文章,还下载了个PPT。研究了半天,终于搞懂后,搜了好多判环和求树的直径的代码,都和我要写的方法不一样。
纠结了好久不敢写,后来脑子疼了,打算乱写一通试试,结果随便调了调竟然就过了。(是太不相信自己了么?
首先,无向图判环,想到用 dfs,但是要记录前驱节点。(但我百度半天没发现这么写的,所以一直不敢肯定自己是对的。。。
然后,如何求树的直径呢?
随便找一个点u ,找到距离 u 最远的点 v。
然后再从 v 出发,找距离 v 最远的点 w,路径(v -> w)就是树的直径。
证明:首先,v 一定是直径的一端。
a) 如果 u 是直径的一端,那么 v 显然是直径的另一端,结论成立。
b) 如果 u 不是直径的一端,那么路径(u->v)一定与直径交于一点 p,且(p->v)一定是直径的一部分,推出 v 是直径的一端,结论成立。
1> 为什么一定存在交点 p?
如果不存在交点 p ,由于树是连通的,那么加若干边使得直径经过(u->v)上的一点 p,直径不会变得更短。
2>为什么(p->v)一定是直径的一部分。
如果不是,(u->v)就不是从 u 到 v 最长的路径。
于是我成功的将判环和求直径用一个 dfs 实现了,233333333。
(既然是树,我不明白为什么大家都要去用 bfs 来求路径长度。。。大概是防止RE)
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e5+3; struct Vertex { int head; }V[N]; struct Edge { int v,w,next; }E[N*10*2]; bool vis[N],tmpv[N]; int top,d[N]; void init() { top = 0; memset(V,-1,sizeof(V)); } void addEdge(int u,int v,int w) { E[top].v = v; E[top].w = w; E[top].next = V[u].head; V[u].head = top++; } bool dfs(int pre,int u) { vis[u] = true; for(int i=V[u].head;~i;i=E[i].next) { int v = E[i].v; if(v == pre) continue; if(vis[v]) return false; d[v] = d[u] + E[i].w; if(!dfs(u,v)) return false; } return true; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { init(); while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } int ans = 0; bool yes = false; memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) { if(vis[i]) continue; memset(d,0,sizeof(d)); if(!dfs(0,i)) { yes = true; break; } int u = max_element(d+1,d+1+n) - d; memcpy(tmpv,vis,sizeof(vis)); memset(vis,false,sizeof(vis)); memset(d,0,sizeof(d)); dfs(0,u); ans = max(ans,*max_element(d+1,d+1+n)); memcpy(vis,tmpv,sizeof(vis)); } if(yes) puts("YES"); else printf("%d\n",ans); } return 0; }