好久没有写过图论的东西了，居然双向边要开两倍空间都忘了，不过数组越界cf居然给我报MLE？？这个题题意特别纠结，一开始一直不懂添加的边长是多长。。。
题意：给你一些点，然后给一些边，注意没有重边 环，接着给你两种操作：
1 x ：求出 x 的集合中最长的边权值
2 x y：合并 x 的集合和 y的集合变成一个集合，并且将 x 集合中任意一个点与 y 集合中任意一个点相连，使合成的集合的任意两个点的最大权值最小，其中两个点相连的权值为1
开始边是固定的，因而建图并两次dfs遍历找树直径，但是不一定所有点是在连一起的所以要找扫一遍。
树直径：无根树中某两个点的距离的最大值，第一遍dfs，以任意一点为起点找到距离最远的点，接着以找到的点起点再来一遍dfs
接着使用并查集，合并两棵树更新权值：(ran[x]+1)/2+(ran[y]+1)/2+1（合并后 两树之间 可以形成的最大权值的最小值）
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=600010;//双向边，开两倍 int fat[Max],ran[Max],vis[Max],len,ega; int head[Max],nnext[Max],to[Max],e; void Init(int n) { e=0; memset(head,-1,sizeof(head)); for(int i=0; i<=n; i++) { fat[i]=i; ran[i]=0; vis[i]=0; } return; } void add(int u,int v) { to[e]=v; nnext[e]=head[u]; head[u]=e++; return; } void dfs(int son,int fat,int now)//遍历树 { vis[son]=1; for(int i=head[son]; i!=-1; i=nnext[i]) { if(to[i]!=fat) dfs(to[i],son,now+1); } if(len<now)//找到最远的点 { len=now; ega=son; } return; } int Find(int x) { if(x==fat[x]) return fat[x]; return fat[x]=Find(fat[x]); } void Union(int x,int y) { int x1=Find(x); int y1=Find(y); if(x1==y1) return; if(x1>y1)//最小数字的得到权值 { fat[x1]=y1; ran[y1]=max(ran[x1],max(ran[y1],(ran[x1]+1)/2+(ran[y1]+1)/2+1));//两棵树合并得到的最小直径 } else { fat[y1]=x1; ran[x1]=max(ran[x1],max(ran[y1],(ran[x1]+1)/2+(ran[y1]+1)/2+1)); } return; } int main() { int n,m,q; int u,v,typ; while(~scanf("%d %d %d",&n,&m,&q)) { Init(n); for(int i=0; i<m; i++) { scanf("%d %d",&u,&v); Union(u,v); add(u,v); add(v,u); } for(int i=1; i<=n; i++) //两次dfs求出树直径 { if(!vis[i]) { len=0; ega=i; dfs(i,i,0); len=0; dfs(ega,ega,0); ran[i]=len;//最小的点赋权值 } } for(int i=0; i<q; i++) { scanf("%d",&typ); if(typ==1) { scanf("%d",&u); v=Find(u); printf("%d ",ran[v]); } else { scanf("%d %d",&u,&v); Union(u,v); } } } return 0; }