HDU4514湫湫系列故事——设计风景线(并查集判环+最长直径)
分类：图论
题目链接：传送门
题意：
先判一个图是否存在换，，不存在的话输出这个图的最长路径。
代码如下：
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include <queue>using namespace std;const int maxn = 1e6+10;int par[maxn/10],head[maxn/10];bool vis[maxn/10];int dis[maxn/10];bool used[maxn/10];struct nod {int to,next,w;} edge[maxn*2];int n,m,ip;void init() {ip=0;memset(head,-1,sizeof(head));memset(used,0,sizeof(used));for(int i=1; i<maxn/10; i++)par[i]=i;}int find_par(int x) {if(par[x]!=x) return par[x] = find_par(par[x]);return par[x];}bool Union(int x,int y) {x=par[x];y=par[y];if(x!=y) {par[y]=x;return true;}return false;}void add(int u,int v,int w) {edge[ip].to=v;edge[ip].w=w;edge[ip].next=head[u];head[u]=ip++;}int max_size;int BFS(int u) {max_size=0;memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));queue<int >Q;Q.push(u);vis[u]=1;int to =u;while(!Q.empty()) {int top = Q.front();used[top]=1;Q.pop();for(int i=head[top]; i!=-1; i=edge[i].next) {int v = edge[i].to;if(!vis[v]) {dis[v]=edge[i].w+dis[top];if(dis[v]>max_size)max_size=dis[v],to=v;vis[v]=1;Q.push(v);}}}return to;}int main() {while(~scanf("%d%d",&n,&m)) {init();bool tag = 0;for(int i=0; i<m; i++) {int u,v,w;scanf("%d%d%d",&u,&v,&w);if(tag) continue;if(!Union(u,v)) tag = 1;add(u,v,w);add(v,u,w);}if(tag) {puts("YES");continue;}int ans = -1;for(int i=1; i<=n; i++) {if(!used[i]) {int st = BFS(i);BFS(st);ans = max(ans,max_size);}}printf("%d\n",ans);}return 0;}/****5 41 2 12 3 22 4 14 5 2***/
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇树的重心及其一些性质
顶0踩0
总结成功的经验能够让人越来越聪明，
