| 合作网络D306 |
| 运行时间限制：1000ms； 运行空间限制：51200KB； |
|
试题描述
|
|
有n个结点，初始时每个结点的父结点都不存在。你的任务是执行若干次Set操作和Query操作，格式如下： □Set u v:把结点u的父结点设为v，距离为|u-v|除以1000的余数。输入保证执行指令前u没有父结点。 □Query u:询问u到根结点的距离。
|
|
输入
|
|
第一行包含两个正整数n和m，表示共有n个结点（编号从1到n），m条指令。接下来的m行每行包含一个指令，其中Set指令的个数小于n。
|
|
输出
|
|
若干行，各行依次对应每一个查询指令的查询结果。
|
|
输入示例
|
|
20 10
Set 2 4
Set 6 9
Set 4 8
Set 5 9
Query 2
Query 4
Set 13 8
Set 11 12
Set 3 9
Query 3
|
|
输出示例
|
|
6 4 6
|
|
其他说明
|
|
数据范围：0<m<10000,m<n,0<n,u,v<20000。提示：并查集相关知识。
|
题解：
经典的并查集问题。每次查祖先的时候顺带把它到祖先的距离更新。
细节请参照代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,f[],dis[];//dis表示它到父亲节点的距离
int h(int x)//并查集的核心部分
{
if(f[x]==x) return x;//它的祖先是它本身，那么就找到真正的“老大”
int tx=f[x],ty=h(f[x]);//tx:存储当前的父节点 ty:继续找
f[x]=ty;//找到了x的祖先
dis[x]+=dis[tx];//dis[tx]的值已经在路径压缩弄好了，加上即可
return ty;
} int main()
{
int i,u=,k=,a,b;
scanf("%d%d",&n,&m);
for(i=;i<=;i++) //千万别忘了初始化
{
f[i]=i;
dis[i]=;
}
char t[];
for(i=;i<=m;i++)
{
cin>>t;
if(t[]=='S')
{
scanf("%d%d",&a,&b);
f[a]=b;//a的祖先是b
dis[a]=abs(a-b)%;//距离的更新
}
else if(t[]=='Q')
{
scanf("%d",&a);
h(a);//查找a到祖先的距离
printf("%d\n",dis[a]);
}
}
return ;
}
D306