带权并查集 poj1182

首先要注意核心代码

int find(int i){
    if(i == fa[i])
        return fa[i];
    int tt = find(fa[i]);
    num[i] = (num[i] + num[fa[i]]) % 3;
    fa[i] = tt;
    return fa[i];
}
不能写成

int find(int i){
    if(i == fa[i])
        return fa[i];
    fa[i] = find(fa[i]);
    num[i] = (num[i] + num[fa[i]]) % 3;
    //fa[i] = tt;
    return fa[i];
}

如果这样的话fa指的就不是他的father而是他的祖先算num的时候会发生错误

而后37,8行不能这样写

num[find(y)] = (num[x] + (3-a) + 3-num[y]) %3;//这是会造成最祖先不是0 接下来find是会错误
fa[find(y)] = fx;

由这件事我们知道做带权并查集时要是可保证最祖先权值为零，预处理出所有要求的最祖先也是一个好习惯。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxa = 50005;
int fa[maxa];
int num[maxa];
int find(int i){
    if(i == fa[i])
        return fa[i];
    int tt = find(fa[i]);
    num[i] = (num[i] + num[fa[i]]) % 3;
    fa[i] = tt;
    return fa[i];
}

int main(){
   //freopen("in.cpp", "r", stdin);
    int n, m;
    int x, y, a;
    scanf("%d%d", &n, &m);
        int sum = 0;
        for(int i = 0; i <= n; i++)
            fa[i] = i, num[i] = 0;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &a, &x, &y);
            //printf("%d %d %d
", a, x, y);
            if(x > n || y > n )//||(x == y && a == 2) )
                sum ++;
            else{
                a --;
                int fx = find(x), fy = find(y);
                if(fx == fy){
                    if((num[x] - num[y] + 3) % 3 != a)
                        sum ++;//,printf("%d %d %d %d
",x, y,  find(x), find(y));
                }else{
                    num[fy] = (num[x] + (3-a) + 3-num[y]) %3;
                    fa[fy]  = fx;
                //printf("%d %d %d %d %d
",x, y, num[x], num[y], sum);
                }
            }
    }
        printf("%d
", sum);

}

View Code

带权并查集 poj1182

相关推荐