【并查集】POJ 2492 :A Bug's Life

POJ 2492 : A Bug’s Life

編号1~n的Bugs，給出不同性别的m對，證明是否有同志的Bugs。

可以看出題目是含有關系的并查集，将1~n歸為男性，n+1~2 * n為女性。

當查詢Find(x) == Find(y)時，證明含有錯誤的清單，則輸出Suspicious bugs found!，

否則則合并x，y（Union（x,y + n）,Union(x + n , y)操作）

代碼

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;

const int MAXNUM =  * ( + );
int id[MAXNUM];
int Size[MAXNUM];
// 初始化
void make_set(int n){
    for(int i =  ; i <= n ; i++){
        id[i] = i;
        Size[i] = ;
    }
}

// 查找父節點
int Find(int p) {
     while (p != id[p]) {
        // 路徑壓縮，會破壞掉目前節點的父節點的尺寸資訊，因為壓縮後，目前節點的父節點已經變了
        id[p] = id[id[p]];
        p = id[p];
    }
    return p;
}

// 合并 p ,q節點
void Union(int p, int q) {
    int pRoot = Find(p);
    int qRoot = Find(q);

    if (pRoot == qRoot) {
        return;
    }
    // 按秩進行合并
    if (Size[pRoot] > Size[qRoot]) {
        id[qRoot] = pRoot;
        Size[pRoot] += Size[qRoot];
    } else {
        id[pRoot] = qRoot;
        Size[qRoot] += Size[pRoot];
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int Case = ;
    int n, m ;
    int p, q;
    int t;
    scanf("%d", &t);
    while(t--){
        bool ans = true;
        scanf("%d %d", &n, &m);
        make_set(n * );
        for(int i =  ; i < m ; i++){
            scanf("%d %d", &p, &q);
            if(Find(p) == Find(q))
                ans = false;
            else{
                Union(p, q + n);
                Union(p + n, q);
            }
        }
        printf("Scenario #%d:\n",Case++);
        if(ans)
            printf("No suspicious bugs found!\n\n");
        else
            printf("Suspicious bugs found!\n\n");
    }

    return ;
}
           

代碼

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;

const int MAXNUM =  + ;
int id[MAXNUM];
int Size[MAXNUM];
int r[MAXNUM];
// 初始化
void make_set(int n){
    for(int i =  ; i <= n ; i++){
        id[i] = i;
        Size[i] = ;
        r[i] = ;
    }
}

// 查找父節點
int Find(int p) {
    while (id[p] != id[id[p]]) {   //如果q不是其所在子樹的根節點的直接孩子
        r[p] = (r[p] + r[id[p]] ) % ;
         id[p] = id[id[p]];          //對其父節點到其爺爺節點之間的路徑進行壓縮
      }
    return id[p];
}

// 合并 p ,q節點
void Union(int p, int q, int d) {
    int pRoot = Find(p);
    int qRoot = Find(q);

    if (pRoot == qRoot) {
        return;
    }
    id[qRoot] = pRoot;
    r[qRoot] = (r[p] - r[q] + d) % ;
}

int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int Case = ;
    int n, m ;
    int p, q;
    int t;
    scanf("%d", &t);
    while(t--){
        bool ans = true;
        scanf("%d %d", &n, &m);
        make_set(n);
        for(int i =  ; i < m ; i++){
            scanf("%d %d", &p, &q);
            if(Find(p) == Find(q) && r[p] == r[q])
                ans = false;
            else{
                Union(p, q , );
            }
        }
        printf("Scenario #%d:\n",Case++);
        if(ans)
            printf("No suspicious bugs found!\n\n");
        else
            printf("Suspicious bugs found!\n\n");
    }

    return ;
}