社区讨论

一个很让人痛苦的错误，留一个帖子

FFishingStar
P1196[NOI2002] 银河英雄传说参与者 7已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@locl2hft
此快照首次捕获于
2023/10/30 15:33
2 年前
此快照最后确认于
2023/11/05 02:44
2 年前
查看原帖
CPP
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int fa[300005];
int dis[300005];
int size[300005];
int find(int x){
    if(fa[x] == x){
        return x;
	}
	int t = fa[x];
	dis[x] += dis[t];
	fa[x] = find(t);
	return fa[x];
}
void join(int x, int y){
	int tx, ty;
	tx = find(x);
	ty = find(y);
    fa[tx] = ty;
    dis[tx] = size[ty];
    size[ty] += size[tx];
//    printf("x = %d, y = %d, size = %d, dis x = %d\n", x, y, size[ty], dis[tx]);
}
int main(){
	int T;
	cin >> T;
	for(int i = 1; i <= 30005; i++){
	    fa[i] = i;
	    size[i] = 1;
	}
	for(int i = 0; i < T; i++){
	    char op;
	    cin >> op;
	    if(op == 'M'){
	    	int x, y;
	    	cin >> x >> y;
	        join(x, y);
		} else {
			int x, y;
			cin >> x >> y;
		    if(find(x) != find(y)){
		        cout << -1 << endl;
			} else {
//				cout << find(x) << " " << find(y) << " " << dis[x] << " " << dis[y] << endl;
			    cout << abs(dis[y] - dis[x]) - 1 << endl;
			}
		}
	}
    return 0;
}
与
CPP
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int fa[300005];
int dis[300005];
int size[300005];
int find(int x){
    if(fa[x] == x){
        return x;
	}
	int t = fa[x];
	fa[x] = find(t);
	dis[x] += dis[t];
	return fa[x];
}
void join(int x, int y){
	int tx, ty;
	tx = find(x);
	ty = find(y);
    fa[tx] = ty;
    dis[tx] = size[ty];
    size[ty] += size[tx];
//    printf("x = %d, y = %d, size = %d, dis x = %d\n", x, y, size[ty], dis[tx]);
}
int main(){
	int T;
	cin >> T;
	for(int i = 1; i <= 30005; i++){
	    fa[i] = i;
	    size[i] = 1;
	}
	for(int i = 0; i < T; i++){
	    char op;
	    cin >> op;
	    if(op == 'M'){
	    	int x, y;
	    	cin >> x >> y;
	        join(x, y);
		} else {
			int x, y;
			cin >> x >> y;
		    if(find(x) != find(y)){
		        cout << -1 << endl;
			} else {
//				cout << find(x) << " " << find(y) << " " << dis[x] << " " << dis[y] << endl;
			    cout << abs(dis[y] - dis[x]) - 1 << endl;
			}
		}
	}
    return 0;
}
有什么区别？ 区别是find函数里
CPP
int find(int x){
    if(fa[x] == x){
        return x;
	}
	int t = fa[x];
dis[x] += dis[t];
fa[x] = find(t);
两个的顺序
这至关重要：第一种11分，第二种AC
为什么？
你在find的过程中其实相当于更新了这个并查集上的值：原本的值在合并后会变得不适用（本质上你这个的“父亲”在路径压缩后是根节点，但是你当前的父亲到根节点的值可能并不对，他可能是他的旧父亲），而需要find更新一遍这才能正确，这玩意坑我半天

回复

共 8 条回复，欢迎继续交流。

正在加载回复...