link

带权并查集做法 (向量)

  • 参考博文
  • 带权并查集与普通并查集的区别主要在find()uni()上 在进行两项操作的同时要对节点的权值进行更新, 参考参考博文的做法, 使用了类似向量的思想

变量解释

  • node中
    • per父节点
    • rel与父节点(即向量指向的节点)的关系
      • 0=>同类 1=>被父节点吃 2=>吃父节点
    • high高度, 本题中没有 (至少我的码里没用…)

合并

-假设有 pa, a, pb, b 四个节点, a 与 b 有关系, 具体如图

  • 将 pb 连接到 pa 时侯, 就可以很容易的得到 pa 与 pb 的关系

  • b->pb + pb->pa = b->a + a->pa 推出pb->pa = b->a + a->pa - b->pb
    转化为代码 node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;

find() (同时压缩路径)

  • 假设有 a, b, c 三个节点, 关系如图

  • 将 c 连接到 a 时

  • c->a = c->b + b->a
    转化为代码node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3;

  • 通过 tmp 进行递归迭代进行路径压缩

code

/**********************************************************
    > File Name : poj-1182-jq.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 22 09:57:18
**********************************************************/
// 282ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
struct nodep{
    int per;
    int high;
    //0=>同类 1=>被父节点吃 2=>吃父节点
    int rel;
}node[50100];
int n, k;
int D[100010];
int X[100010];
int Y[100010];

void init(){
    for(int i = 0 ; i < n; i++){
        node[i].per = i;
        node[i].rel = 0;
    }
}


int find(int a){
    if(node[a].per == a) return a;
    else{
        int tmp = node[a].per;
        node[a].per = find(node[a].per);
        node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3;
        return node[a].per;
    }
}

void uni(int a, int b, int d){
    int pa = find(a);
    int pb = find(b);
    if(pa == pb) return ;
    /*
    if(node[pa].high > node[pb].high){
        node[pb].per = pa;
        node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;
    }else if(node[a].high < node[b].high){
        node[a].per = b;
        node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3;
    }else{
        node[a].per = b;
        node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3;
        node[pb].high++;
    }
    合并树 注意:被 a 吃,所以以 a 的根为父
    也就是说, 不能按照白书上介绍的那样进行压缩操作
    */

    node[pb].per = pa;
    node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;
}

bool same(int a, int b){
    return find(a) == find(b);
}

int getrel(int a, int b){
    // 所求为 a => b 的关系
    find(a);
    find(b);
    return (node[a].rel - node[b].rel + 3) % 3;
}
void solve(){
    init();
    int ans = 0;
    for(int i = 0; i < k; i++){
        int d = D[i];
        int x = X[i] - 1;
        int y = Y[i] - 1;
        if(d == 2 && x == y){
            ans++;
            continue;
        }
        if(x < 0 || x >= n || y < 0 || y >= n){
            ans++;
            continue;
        }

        if(same(x, y)){
            if(d == 1 && getrel(x, y) != 0) ans++;
            if(d == 2 && getrel(x, y) != 2) ans++;
        }
        uni(x, y, d - 1);
    }
    printf("%d", ans);
}
int main(){
    cin >> n >> k;
    for(int i = 0; i < k; i++){
        scanf("%d %d %d", D + i, X + i, Y + i);
    }
    solve();
    return 0;
}

白书做法 (分类)

/**********************************************************
    > File Name : poj-2236.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 20 21:09:04
**********************************************************/
// 329ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int par[150010];
int high[150010];
int D[100010];
int X[100010];
int Y[100010];

int n, k;
void init(int n){
    for(int i = 0; i < n; i++){
        par[i] = i;
        high[i] = 0;
    }
}

int find(int a){
    if(par[a] == a) return a;
    else{
         return par[a] = find(par[a]);
    }
}

void unite(int a, int b){
    a = find(a);
    b = find(b);
    if(a == b) return ;

    if(high[a] > high[b]){
        par[b] = a;
    }else if(high[a] < high[b]){
        par[a] = b;
    }else{
        par[a] = b;
        high[b]++;
    }
}

bool same(int a, int b){
    return find(a) == find(b);
}

void solve(){
    init(n * 3);
    int ans = 0;
    for(int j = 0; j < k; j++){
        int d = D[j];
        int x = X[j] - 1;
        int y = Y[j] - 1;
        if(x < 0 || x >= n || y < 0 || y >= n){
            ans++;
            continue;
        }

        if(d == 1){
            if(same(x, y + n) || same(x, y + 2 * n)){
                ans++;
            }else{
                unite(x, y);
                unite(x + n, y + n);
                unite(x + 2 * n, y + 2 * n);
            }
        }

        if(d == 2){
            if(same(x, y) || same(x, y + 2 * n)){
                ans++;
            }else{
                unite(x, y + n);
                unite(x + n, y + 2 * n);
                unite(x + 2 * n, y);
            }
        }
    }
    cout << ans << endl;
}

int main(){
    cin >> n >> k;
    int din, xin, yin;
    for(int i = 0; i < k; i++){
        scanf("%d %d %d", D + i, X + i, Y + i);
    }
    solve();
    return 0;
}