软件综合课设做网站,广告公司做网站,淄博抖音关键词优化,wordpress收费版怎么激活#x1f4af; 博客内容#xff1a;并查集 #x1f600; 作 者#xff1a;陈大大陈 #x1f680; 个人简介#xff1a;一个正在努力学技术的准C后端工程师#xff0c;专注基础和实战分享 #xff0c;欢迎私信#xff01; #x1f496; 欢迎大家#xff1a;这里是C… 博客内容并查集 作 者陈大大陈 个人简介一个正在努力学技术的准C后端工程师专注基础和实战分享 欢迎私信 欢迎大家这里是CSDN我总结知识和写笔记的地方喜欢的话请三连有问题请私信 目录
初版
路径压缩版
两个例题
几张桌子
是不是亲戚 并查集是一种挺实用的数据结构可以处理一些不相交集合的合并问题。
基本操作有初始化合并查找统计。
咱们先来个初版再优化一下。
初版
#includebits/stdc.h
using namespace std;
const int N 10000;
int fa[N];
void init(int N)//初始化
{for (int i 1; i N; i){fa[i] i;}
}
int find(int i)//查找
{return i fa[i] ? i : find(fa[i]);
}
void Union(int i, int j)//合并
{int x find(i);int y find(j);fa[x] y;
}
这种并查集查找的效率太低最坏情况的时间复杂度能达到O(N)。
我们就针对它优化。
路径压缩版
#includebits/stdc.h
using namespace std;
const int N 10000;
int fa[N];
void init(int N)
{for (int i 1; i N; i){fa[i] i;}
}
int find(int i)
{if (i fa[i]){return i;}else{fa[i] find(fa[i]);return fa[i];}
}
void Union(int i, int j)
{int x find(i);int y find(j);fa[x] y;
}
上面的时间复杂度最好能有O(1)。
实现方式是记忆化搜索用数组存储好所需结果需要时就不用再次递归了。
来看两个例题巩固一下。
两个例题
几张桌子
How Many Tables并查集
Problem - 1213 (hdu.edu.cn)
题目
Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
Input
The input starts with an integer T(1T25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1N,M1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!B), that means friend A and friend B know each other. There will be a blank line between two cases.
Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
Sample Input
2 5 3 1 2 2 3 4 5
5 1 2 5
Sample Output
2
4
思路每个人是一个数组两个数组内存的数如果相同代表认识并成为一桌每个数组内刚开始都是自身编号
给你们一组特殊测试数据
输入
1
5 4
1 2
1 3
4 3
3 4
输出
2
#define _CRT_SECURE_NO_WARNINGS
#includebits/stdc.h
using namespace std;
const int N 1050;
int fa[N];
void init()
{for (int i 1; i N; i){fa[i] i;}
}
int find(int i)
{if (i fa[i]){return i;}else{fa[i] find(fa[i]);return fa[i];}
}
void Union(int i, int j)
{int x find(i);int y find(j);fa[x] y;
}
int main()
{int t, x, y, n, m;cin t;//t个测试while (t--){cin n m;init();for (int i 1; i m; i){cin x y;Union(x, y);//合并x和y}int ans 0;for (int i 1; i n; i)//统计有多少个集{if (fa[i] i)ans;}cout ans endl;}return 0;}
是不是亲戚 #define _CRT_SECURE_NO_WARNINGS
#includebits/stdc.h
using namespace std;
const int N 1050;
int fa[N];
void init()
{for (int i 1; i N; i){fa[i] i;}
}
int find(int i)
{if (i fa[i]){return i;}else{fa[i] find(fa[i]);return fa[i];}
}
void Union(int i, int j)
{int x find(i);int y find(j);fa[x] y;
}
int main()
{int n, m, n2;;cin n m;init();for (int i 0; i m; i){int x, y;cin x y;Union(x, y);}cin n2;for (int i 0; i n2; i){int x, y;cin x y;if (find(x) find(y))cout Yes endl;elsecout No endl;}return 0;}
