10pts,玄关求条,只对了第一个点
查看原帖
10pts,玄关求条,只对了第一个点
1122029
icebear233楼主2025/8/4 15:16
#include<bits/stdc++.h>
using namespace std;
int n,ans,m,q;
vector<int> g[300005];
int f1[300005],f2[300005];
int fa[300005];
int f[300005];
bool vis[300005];
int find(int x){
	while(x==fa[x]){
		return x;
	}
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int u=find(x),v=find(y);
	fa[u]=v;
}
void dfs(int u,int fa){
	f1[u]=f2[u]=0;
	for(int v,i=0;i<g[u].size();i++){
		v=g[u][i];
		if(v!=fa){
			dfs(v,u);
			int t=f1[v]+1;
			if(t>f1[u]){
				f2[u]=f1[u];
				f1[u]=t; 
			}
			else if(t>f2[u]){
				f2[u]=t;
			}
		}
	}
	
	ans=max(ans,f1[u]+f2[u]);
}

int main(){ 
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
		merge(u,v);
	}
	for(int i=1;i<=n;i++){
		if(fa[i]!=i||vis[i]){
			continue;
		}
		ans=0;
		dfs(i,0);
		f[i]=ans;
		vis[i]=1;
	}
	while(q--){
		int op,x,y;
		cin>>op;
		if(op==1){
			cin>>x;
			cout<<f[find(x)];
		}
		else{
			cin>>x>>y;
			x=find(x),y=find(y);
			if(x==y){
				continue;
			}
			int t=max((f[x]+1)/2+(f[y]+1)/2+1,max(f[x],f[y]));
			merge(x,y);
			f[find(x)]=t;
		}
		
	}

	
	return 0;
}
2025/8/4 15:16
加载中...