20pts,只过了#1,#3求助
查看原帖
20pts,只过了#1,#3求助
581574
ssfx2019s005楼主2024/10/10 15:27
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,q;
const int N=6e5+15;
int e[N],ne[N],h[N],idx,vis[N];
int f[N],mxl;
int fa[N],d[N];
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return f*x;
}
int find_zu(int x){
	if(fa[x]!=x) fa[x]=find_zu(fa[x]);
	return fa[x];
}
void add_in(int x,int y){
	e[++idx]=y; ne[idx]=h[x]; h[x]=idx;
}
void dfs(int u,int pre){
	f[u]=0;
	for(int i=h[u];i;i=ne[i]){
		int v=e[i];
		if(v==pre) continue;
		dfs(v,u);
		mxl=max(mxl,f[u]+f[v]+1);
		f[u]=max(f[u],f[v]+1);
	}
	f[u]=0;
}
int main(){
	cin>>n>>m>>q;
	int x,y,z;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		x=read(); y=read();
		add_in(x,y);
		add_in(y,x);
		fa[find_zu(x)]=find_zu(y); 
	}
	int op;
	for(int i=1;i<=n;i++){
		if(vis[i] || fa[i]!=i) continue;
		vis[i]=1;
		mxl=0;
		dfs(i,0);
		d[i]=mxl;
	}
	while(q--){
		op=read();
		if(op==1){
			x=read();
			cout<<d[find_zu(x)]<<endl;
		}
		else if(op==2){
			x=read(); y=read();
			x=find_zu(x); y=find_zu(y);
			if(x==y) continue;
			int t=((d[x]+1)/2)+((d[y]+1)/2)+1;
			t=max(t,max(d[x],d[y]));
			fa[find_zu(x)]=find_zu(y);
			d[find_zu(y)]=d[find_zu(x)]=t;
		}
	}
	return 0;
} 
2024/10/10 15:27
加载中...