为什么这个题题解这么少啊
是不是大家都太强不屑于做板子题啊
//来自算法基础课
维护连通块size的并查集
一、初始化
void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}
二、找祖源
int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}
三、合并连通块
void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}
四、询问是否连通
bool ask(int a,int b) {
return find(a)==find(b);
}
特别注意:
size只有祖节点的有意义
要特别注意所有处理size的地方,都要“归根结底”
完整CODE
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;
void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}
int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}
void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}
bool ask(int a,int b) {
return find(a)==find(b);
}
int main() {
read(n),read(m);
init();
while(m--) {
cin>>act;
if(act=="C") {
read(a),read(b);
if(!ask(a,b)) merge(a,b);
} else if(act=="Q1") {
read(a),read(b);
ask(a,b) ? printf("Yes\n") : printf("No\n");
} else {
read(a);
printf("%d\n",size[find(a)]);
}
}
return 0;
}
给自己打个标记,更新Size的时候看看a,b是否已经在一个集合,血的教训
## QAQ
666
11月后的我看到你的评论ac了。。
合并那里是不是错了呀。在合并之后应该把a集合的size清零才对吧。否则对于这样的输入序列会出错:
C 1 2
C 2 1
Q2 1
确实是写错了。是因为作者在写的时候没有判断a、b是否已经处于同一个并查集。如果已经处于同一并查集,直接跳过后面的
就可以了。当然你的做法也是可以的。只不过特判之后,a的size不用改也可以,因为a这边的连通块父节点都是b的父节点了。
int x=find(a);
int y=find(b);
if(x!=y){ p[x]=y;
size[y]+=size[x];}
//为什么一定要x替换find(a),不然结果就不一样了
第二句如果
p[find[a]] = find[b]
那么就改变了
find[a]
应该与改变前的比较所以用
x,y
取出两个数值进行比较,确保两次操作互不干扰先把size加起来再合并,不然先合并再加就是自己和自己祖先的size相加了
对。或者像y总那样先建两个变量保存原有值,这样什么顺序都不怕了。
为啥size[y] += size[x];这个可以记录连通块的总数哇,其他我都懂就这个不知道为啥一直理解不了
size[]记录的是每个集合各自的总数量(且只有集合根节点的有意义,枝节上的size并没有维护),相加自然就是两个连通块的总数
l两个节点之间连一条边,就是指将两个节点的祖宗节点连接到一起,这理解我怎么觉得和题意不太相符和啊。
我觉得也是
命名为
find()
会不会有潜在的名称冲突?和C++某些库函数```#include[HTML_REMOVED]
#define read(x) scanf(“%d”,&x)
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;
void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}
int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}
void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}
bool ask(int a,int b) {
return find(a)==find(b);
}
int main() {
read(n),read(m);
init();
while(m–) {
cin>>act;
if(act==”C”) {
read(a),read(b);
if(!ask(a,b)) merge(a,b);
} else if(act==”Q1”) {
read(a),read(b);
ask(a,b) ? printf(“Yes\n”) : printf(“No\n”);
} else {
read(a);
printf(“%d\n”,size[find(a)]);
}
}
return 0;
}
```
这个题为什么用cin >> op 好像就不行
op是string类, 不能直接用 cin 读入, char op[5] 就可以了
可以用cin读入
使用头文件#include[HTML_REMOVED]就可以
里面是 string
为什么源代码会报错呢
好清晰 赞
#include [HTML_REMOVED]
using namespace std;
const int N = 100010;
int n,m;
int fa[N],Size[N];
// 并查集
int find(int u)
{
if(fa[u] != u) fa[u] = find(fa[u]);
return fa[u];
}
// 合并两个连通块
void merge(int a,int b)
{
int x = find(a);
int y = find(b);
fa[x] = y;
Size[y] += Size[x];
}
bool check(int a,int b)
{
return fa[a] == fa[b];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n;i++)
{
fa[i] = i;
Size[i] = 1;
}
string op;
while (m – )
{
cin >> op;
int a,b;
if(op == “C”)
{
cin >> a>> b;
if(find(a) == find(b)) continue;
merge(a,b);
}
else if(op == “Q1”)
{
cin >> a>> b;
if(check(a,b))
cout <<”Yes”;
else cout << “No”;
cout << endl;
}
else
{
cin >> a;
cout <<Size[find(a)] << endl;
}
}
return 0;
}
大哥,看看俺的为啥过不去,我wa的数据和我输出的明明一模一样啊!!!
加一句
if(find(a)==find(b)) continue;
为什么要先计算再合并呢
因为合并后两个根是一样的了,咋还能计算出size的和呢?
合并后再size相加,就相当于翻倍了
正解,我也犯了同样的错误啊
大哥,看看俺的为啥过不去,我wa的数据和我输出的明明一模一样啊!!!
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
int n,m,a,b;
int p[100100],t[100100];
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i) p[i] = i;
for(int i=1;i<=n;i) t[i] = 1;
while(m–)
{
string s;
cin>>s;
if(s==”C”){
cin>>a>>b;
t[find(b)]+=t[find(a)];
p[find(a)] = find(b);
}
“C”操作判断里没有判重吧
“’
if(find(a) == find(b)) continue;
“’
请问为啥要判重呀,还有题目里a,b可能相同,意味着什么吗
不判重,这个t数组的数会增大一倍吧
根节点的size数组就会翻倍,误认为是两个不一样的数组合并,其实是两个相同的数组合并
大哥 讲讲为啥wa 呗
merge1 里面应该是
s[find(a)] += s[find(b)];
只有根节点的s[] 有效真心不错,点赞
fa[x] = y;请我一下这句什么意思(菜鸟询问)
合并集合啊
把节点
x
的父节点设为节点y
,相当于把x
这个点/树挂载到y
下面,合并成一个fa[x] = y;请我一下这句什么意思(菜鸟询问)
条理很清新,真心不错。
非常不错,非常清晰
非常不错