[NOI2001] 食物鏈

題目描述

動(dòng)物王國中有三類動(dòng)物 \(A,B,C\)，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。

現(xiàn)有 \(N\) 個(gè)動(dòng)物，以 \(1 \sim N\) 編號(hào)。每個(gè)動(dòng)物都是 \(A,B,C\) 中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說法對(duì)這 \(N\) 個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：

• 第一種說法是 1 X Y，表示 \(X\) 和 \(Y\) 是同類。
• 第二種說法是2 X Y，表示 \(X\) 吃 \(Y\)。

此人對(duì) \(N\) 個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出 \(K\) 句話，這 \(K\) 句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。

• 當(dāng)前的話與前面的某些真的話沖突，就是假話；
• 當(dāng)前的話中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假話；
• 當(dāng)前的話表示 \(X\) 吃 \(X\)，就是假話。

你的任務(wù)是根據(jù)給定的 \(N\) 和 \(K\) 句話，輸出假話的總數(shù)。

輸入格式

第一行兩個(gè)整數(shù)，\(N,K\)，表示有 \(N\) 個(gè)動(dòng)物，\(K\) 句話。

第二行開始每行一句話（按照題目要求，見樣例）

輸出格式

一行，一個(gè)整數(shù)，表示假話的總數(shù)。

樣例 #1

樣例輸入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

樣例輸出 #1

3

提示

對(duì)于全部數(shù)據(jù)，\(1\le N\le 5 \times 10^4\)，\(1\le K \le 10^5\)。

題解

思路分析

題目中涉及到需要快速得出ABC三類之間的關(guān)系，那么明顯可以考慮并查集。

【方法1】帶權(quán)并查集
d[u] 表示 x 與其對(duì)應(yīng)根節(jié)點(diǎn) root 的關(guān)系，0 表示同類，1 表示吃，2 表示被吃。

int find(int u) {
    if (u != p[u]) {
        int fa = p[u];
        p[u] = find(p[u]);
        d[u] = (d[u] + d[fa]) % 3;
    }
    return p[u];
}

// (x,y) 同類合并
int a = find(x), b=find(y);
d[x] + d[a] = d[y]. --> d[a] = (d[y] - d[x] + 3) % 3;

// (x eat y) 合并
d[x] + d[a] = d[y] + 1. --> d[a] = (d[y] - d[x] + 4) % 3;

【方法1】擴(kuò)展域并查集
將 p[] 數(shù)組擴(kuò)展為原數(shù)組的 3 倍，p[1~n] 為 A 類，p[n+1~n2] 為 B 類，p[n2+1~n*3] 為 C 類。

也就是說 (u eat u+n), (u+n eat u+n2) , (u+n2 eat u)

// (x,y) 同類合并
p[find(x)] = find(y);
p[find(x + n)] = find(y + n);
p[find(x + n * 2)] = find(y + n * 2);

// (x eat y) 合并
p[find(x)] = find(y + n * 2);
p[find(x + n)] = find(y);
p[find(x + n * 2)] = find(y + n);

程序?qū)崿F(xiàn)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10, INF = 0x3f3f3f3f;
int n, k, p[N * 3], d[N * 3];

int find(int u) {
    if (u != p[u]) {
        int fa = p[u];
        p[u] = find(p[u]);
        d[u] = (d[u] + d[fa]) % 3;
    }
    return p[u];
}
// 帶權(quán)并查集
int solve1() {
    int op, x, y, ans = 0;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) p[i] = i, d[i] = 0;
    while (k--) {
        cin >> op >> x >> y;
        if (x > n || y > n) { ans++; continue; }
        int a = find(x), b = find(y);
        if (op == 1) {  // x-y 同類
            if (a == b && (d[x] - d[y] + 3) % 3) ans++;
            if (a != b) {
                p[a] = b;
                d[a] = (d[y] - d[x] + 3) % 3;
            }
        } else {  // x eat y
            if (a == b && (d[x] - d[y] + 3) % 3 != 1) ans++;
            if (a != b) {
                p[a] = b;
                d[a] = (d[y] - d[x] + 4) % 3;
            }
        } 
    }
    cout << ans << endl;
    return 0;
}

// 擴(kuò)展域并查集
int solve2() {
    int op, x, y, ans = 0;
    cin >> n >> k;
    for (int i = 0; i <= n * 3; i++) p[i] = i;
    while (k--) {
        cin >> op >> x >> y;
        if (x > n || y > n) { ans++; continue; }
        if (op == 1) {  // x-y 同類
            if (find(x) == find(y + n) || find(y) == find(x + n)) {
                ans++; continue;
            }
            p[find(x)] = find(y);
            p[find(x + n)] = find(y + n);
            p[find(x + n * 2)] = find(y + n * 2);
        } else {  // X eat y   (x 吃 x+n)
            if (find(x) == find(y) || find(x) == find(y + n)) {  
                ans++; continue;
            }
            p[find(x)] = find(y + n * 2);
            p[find(x + n)] = find(y);
            p[find(x + n * 2)] = find(y + n);
        }
    }
    cout << ans << endl;
    return 0;
}
int main() {
    solve1();
    // solve2();
}