【打CF，学算法——四星级】CodeForces 455C Civilization (【详解】并查集+树的直径)
扫描二维码
随时随地手机看文章
【CF简介】
提交链接：CF 455C
题面：
C. Civilization time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Andrew plays a game called "Civilization". Dima helps him.
The game has n cities and m bidirectional roads. The cities are numbered from 1 to n. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct citiesv1, v2, ..., vk, that there is a road between any contiguous citiesvi andvi + 1 (1 ≤ i < k). The length of the described path equals to(k - 1). We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.
During the game events of two types take place:
Andrew asks Dima about the length of the longest path in the region where cityx lies. Andrew asks Dima to merge the region where city x lies with the region where cityy lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them.
Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.
Input
The first line contains three integers n,m,q (1 ≤ n ≤ 3·105;0 ≤ m < n; 1 ≤ q ≤ 3·105) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.
Each of the following m lines contains two integers,ai andbi (ai ≠ bi;1 ≤ ai, bi ≤ n). These numbers represent the road between citiesai andbi. There can be at most one road between two cities.
Each of the following q lines contains one of the two events in the following format:
1 xi. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains cityxi (1 ≤ xi ≤ n).2 xiyi. It is the request Andrew gives to Dima to merge the region that contains cityxi and the region that contains cityyi (1 ≤ xi, yi ≤ n). Note, thatxi can be equal toyi. Output
For each event of the first type print the answer on a separate line.
Examples Input
6 0 6 2 1 2 2 3 4 2 5 6 2 3 2 2 5 3 1 1
Output
4
题意：
题目给出一张图，图中原有n个点，m条边，且m<n，且两个点之间没有重边，且两点之间最多只有一条路径。后续有两种操作，操作一，询问某节点所在的联通块上最长的链的长度。操作二，将两个联通块相连，要求相连后形成的联通块的最大长度尽量小。（如果两点原就在一个联通块，就不需要连接了）
解题：
第一次写求树的直径，其实也不难，首先在一个联通块上随意找一个出发，求得该点可以到的最远点的位置，并从最远点反向再进行dfs一遍，此时的最大值就为树的直径（树的直径指的是树上最长的链的长度）。因为，任意从树上某一点出发，能到的最远点一定在树的直径上，故可以反向dfs，求得最优值。
可以用并查集的方式来维护节点的集合关系。当合并两个集合时，为了使合并后得到的树的直径最小，会采取在两颗树的直径的中间点位置相连，这样就最小化了最长链的优势，从而满足了题意，将新得到的联通块合并（更新fa数组），同时更新代表节点对应的val值。
相关知识点：
并查集入门
代码：
#include#include#include#include#include#include#include#define maxn 300005
using namespace std;
//存储边
struct edge
{
int u,v,nxt;
}store[maxn*2];
//cur为当前dfs的起点，max_len最大长度,p最远点位置
int head[maxn],cnt=0,fa[maxn],val[maxn],cur,max_len,p;
//访问标记数组
bool vis[maxn];
//添加双向边
void addedge(int u,int v)
{
store[cnt].nxt=head[u];
head[u]=cnt;
store[cnt].u=u;
store[cnt++].v=v;
store[cnt].nxt=head[v];
head[v]=cnt;
store[cnt].v=u;
store[cnt++].u=v;
}
//dfs求树的直径，pre是树的前驱节点，避免回去
//flag在第一次时不标记，第二次反向时标记
void dfs(int x,int pre,int step,int flag)
{
vis[x]=flag;
fa[x]=cur;
val[x]=step;
if(val[x]>max_len)
{
max_len=val[x];
p=x;
}
for(int i=head[x];~i;i=store[i].nxt)
{
if(store[i].v!=pre&&!vis[store[i].v])
dfs(store[i].v,store[i].u,step+1,flag);
}
}
//找出集合代表元素，同时进行路径压缩
int Find(int x)
{
return fa[x]!=x?fa[x]=Find(fa[x]):x;
}
//合并两个集合，并更新最长链长度
void Union(int a,int b)
{
int tmp,ta,tb;
ta=Find(a);
tb=Find(b);
tmp=max((val[ta]+1)/2+(val[tb]+1)/2+1,max(val[ta],val[tb]));
fa[ta]=tb;
val[tb]=tmp;
}
int main()
{
int n,m,q,a,b,tmp,op,ta,tb;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
cnt=0;
scanf("%d%d%d",&n,&m,&q);
//构图
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
//初始化
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
cur=i;
max_len=0;
p=0;
dfs(i,-1,0,0);
//可能该点没有边，需注意
if(p!=0)
dfs(p,-1,0,1);
val[fa[p]]=max_len;
}
}
//操作
for(int i=0;i<q;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&a);
ta=Find(a);
printf("%dn",val[ta]);
}
else
{
scanf("%d%d",&a,&b);
ta=Find(a);
tb=Find(b);
if(ta==tb)
continue;
else
Union(a,b);
}
}
return 0;
}
下载文档
