Civilization
#include <iostream>
#include <vector>
#include <stdio.h>
#define sf(i) scanf("%d", &i)
#define pf(i) printf("%d\n", i)
#define pb push_back
using namespace std;
const int N = 3e5 + 1;
vector<int> g[N];
int parent[N];
int diameter[N];
bool isUsed[N];
int n, m, q, maxi, maxiv;
int rad(int a)
{
return (diameter[a] + 1) / 2;
}
int find(int a)
{
if(parent[a] == a)
{
return a;
}
return parent[a] = find(parent[a]);
}
void unite1(int a, int b)
{
a = find(a);
b = find(b);
if(a > b)
swap(a, b);
parent[b] = a;
}
void unite(int a, int b)
{
a = find(a);
b = find(b);
if(a > b)
{
swap(a, b);
}
parent[b] = a;
diameter[a] = max(rad(a) + rad(b) + 1, max(diameter[a], diameter[b]));
}
void dfs(int v, int depth, int p)
{
if(depth > maxi)
{
maxi = depth;
maxiv = v;
}
for(int i = 0; i < g[v].size(); i++)
{
if(g[v][i] == p)
continue;
dfs(g[v][i], depth + 1, v);
}
}
int findLongestWay(int i)
{
maxi = -1;
dfs(i, 0, -1);
maxi = -1;
dfs(maxiv, 0, -1);
return maxi;
}
int main()
{
int a, b, x, y, num;
sf(n), sf(m), sf(q);
for(int i = 0; i <= n; i++)
{
parent[i] = i;
diameter[i] = 0;
isUsed[i] = false;
}
for(int i = 0; i < m; i++)
{
sf(a), sf(b);
g[a].pb(b);
g[b].pb(a);
if(find(a) != find(b))
unite1(a, b);
}
for(int i = 1; i <= n; i++)
{
int p = find(i);
if(!isUsed[p])
{
isUsed[p] = true;
diameter[p] = findLongestWay(i);
}
}
for(int i = 0; i < q; i++)
{
sf(num);
if(num == 1)
{
sf(x);
x = find(x);
pf(diameter[x]);
}
else
{
sf(x), sf(y);
if(find(x) != find(y))
unite(x, y);
}
}
return 0;
}
Comments
Post a Comment