The Tree-planting Day and Simple Disjoint Sets
First I have to say: I have poor English. I am too young, too simple, sometimes naïve.
It was tree-planting day two weeks ago. SHENBEN dph taught us a lot about tree-planting and the disjoint sets. It was useful and valuable for a JURUO like me. I admire all SHENBENs and orz all of them!
How to plant a tree?
First of all, you should know how to make "parent arrays". It is good, isn't it? Using an array f[] you can put information about someone's father. Use f[i], i is an element's index, and f[i] means the father's index.
And we can use disjoint sets now:
- value all elements in array f[] as the index itself. It means all elements' father are themselves, and they any of them is a single set.
- to union two sets, use f[find(y)] = find(x); code. This means one set "tree" is the father of another.
- to see if one and another are in a set, use if (find(x) == find(y)) to determine.
But how to union sets? You can regard this method as making a tree. We can link two trees into one tree, so the question of how many continuous blocks equals the question of how many trees.
And how to find one's daddy ancestor? Using DFS can help a lot. If A is the father of itself, it is the top ancestor. Or, it must we can DFS its father B then (we can make the top ancestor C we found the father of A. It can save time.
Disjoint-set data structure
So it's simple as these codes: (LUOGU P3367 Disjoint Sets)
/* Luogu P3367 并查集
* Au: GG
*/
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = + ;
int n, m, z, x, y, f[maxn];
int find(int k) { // find father
return f[k] == k ? k : f[k] = find(f[k]);
}
int main() {
//freopen("p3367.in", "r", stdin);
scanf("%d%d", &n, &m);
while (n--) f[n] = n;
while (m--) {
scanf("%d%d%d", &z, &x, &y);
if (z == ) {
f[find(y)] = find(x);
} else {
if (find(x) == find(y)) printf("Y\n");
else printf("N\n");
}
}
return ;
}
Yes yes, it's quite simple at first. That's why we love mathematics computer science.
最新文章
- CSS3之盒子模型
- python目前最好用的IDE——pycharm
- java对xml文件做增删改查------摘录
- python字典copy()方法
- HDU 5433 Xiao Ming climbing
- Linq 中的distinct去重
- Android上运行本地c
- 深入浅出—JAVA(8)
- 理解Vue中的Render渲染函数
- [LeetCode] Find Permutation 找全排列
- SVM探讨
- MVC项目实践,在三层架构下实现SportsStore-11,使用Knockout实现增删改查
- Logstash进程杀不掉
- 18. socket io
- postgresql逻辑结构--用户及权限管理（七）
- python的三个函数（eval、exec、complie）和python版RMI
- System.Zip
- 关于Sql注入的那些事
- 时屏蔽ios和android下点击元素时出现的阴影
- 网站定时任务IIS配置