您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1182 食物鏈：擴展並查集維護物種捕食關係

編輯：C++ 入門

問題描述

三類動物 A、B、C 成環捕食：A→B→C→A。N 隻動物（≤ 50000），K 句陳述（≤ 100000）：

1 X Y：X、Y 同類
2 X Y：X 吃 Y

判斷假話數（衝突、編號越界、自吃）。

擴展並查集設計

每個動物對應 3 個節點：x (本體)、x+N (被其吃)、x+2N (吃其)。

同類：union(x, y), union(x+N, y+N), union(x+2N, y+2N)
X 吃 Y：union(x, y+N), union(x+N, y+2N), union(x+2N, y)
衝突檢查：同類時 find(x) == find(y+N) 等；捕食時 find(x) == find(y) 等

完整程式碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 50002;
int parent[MAXN * 3];

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int x, int y) { x = find(x); y = find(y); if (x != y) parent[x] = y; }
bool same(int x, int y) { return find(x) == find(y); }

int main() {
    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1; i <= 3*n; i++) parent[i] = i;
    int lie = 0;
    while (k--) {
        int d, x, y; scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n || x < 1 || y < 1 || (d == 2 && x == y)) { lie++; continue; }
        if (d == 1) { // 同類
            if (same(x, y+n) || same(x, y+2*n)) lie++;
            else { unite(x,y); unite(x+n,y+n); unite(x+2*n,y+2*n); }
        } else { // X 吃 Y
            if (same(x, y) || same(x, y+2*n)) lie++;
            else { unite(x, y+n); unite(x+n, y+2*n); unite(x+2*n, y); }
        }
    }
    cout << lie << endl;
    return 0;
}