題目連結

題目

題目描述

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B，B吃C，C吃A。

現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們並不知道它到底是哪一種。

有人用兩種說法對這N個動物所構成的食物鏈關係進行描述：

第一種說法是「1 X Y」，表示X和Y是同類。

第二種說法是「2 X Y」，表示X吃Y。

此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

1） 當前的話與前面的某些真的話衝突，就是假話；

2） 當前的話中X或Y比N大，就是假話；

3） 當前的話表示X吃X，就是假話。

你的任務是根據給定的N（1≤N≤50,000）和K句話（0≤K≤100,000），輸出假話的總數。

輸入描述

第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。

輸出描述

只有一個整數，表示假話的數目。

範例1

輸入

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

輸出

3

說明

題解

方法一

知識點：並查集。

用權值代表其關於根節點的種類，根節點設為 \(0\) ，其他的同類為 \(0\) ，根節點是獵物為 \(1\) ，根節點是天敵為 \(2\) 。

因為種類形成環狀具有傳遞性關係，因此路徑壓縮可以利用自身權值加父節點路徑壓縮後的權值對 \(3\) 取模即可，遞迴實現。

合併集合時，已知兩個節點 \(a\) 和 \(b\) 路徑壓縮後的權值以及\(a\) 關於 \(b\) 的權值，要求出集合根節點 \(A\) 認 \(B\) 為父後的權值，因為具有環狀傳遞性，所以可以利用向量的思想，\(\vec{AB} = -\vec{aA}+\vec{ab}+\vec{bB}\) ，隨後對 \(|\vec{AB}|\) 模 \(3\) 即可，注意不要出現負數。

如果給出的關係的兩個物件已經在同一個關係集合，那麼檢查他們關係是否和給出的條件吻合，即 \(\vec{ab} == \vec{aA} - \vec{bA}\) ，左邊是條件右邊是已有的關係，不吻合的答案加一。

時間複雜度 \(O(k\log n + n)\)

空間複雜度 \(O(n)\)

方法二

知識點：並查集。

實際上第一種解法較為繁瑣，我們只關心條件之間是否矛盾，即給出的條件的兩個物件已經建立了關係，檢測已有關係和給出的關係是否矛盾。因此可以用擴充套件域並查集，其把元素的所有可能種類擴充套件各個獨立元素，只對有具體種類的元素建立關係集合中的具體等價類（等價類的元素會同時出現），而不把相關的具體等價類並在一個集合產生完整的關係集合，利用權值進行相對分類（帶權並查集是記錄了一整個關係集合，並用權值做了相對根節點的關係劃分），而這對於檢測矛盾已經足夠了。

具體地說，一個動物元素只有三種種類，我們記為 \(A\)，\(B\)，\(C\)，其中 \(A\) 吃 \(B\) ， \(B\) 吃 \(C\) ， \(C\) 吃 \(A\) 。擴充套件域並查集把每個動物元素擴充套件成這 \(3\) 個有具體種類的動物元素，分別放在 $[1,n],[n+1,2n],[2n+1，3n] $ 中。

假設給出 \(a\) 吃 \(b\)，則會合並三個等價類 \([a]\) 與 \([b+n]\) ， \([a+n]\) 與 \([b+2n]\) ， \([a+2n]\) 與 \([b]\) ，表示 \(a\) 是 \(A\) 時 \(b\) 一定是 \(B\)， \(a\) 是 \(B\) 時 \(b\) 一定是 \(C\)，\(a\) 是 \(C\) 時 \(b\) 一定是 \(A\) ，這樣就根據條件合併了兩個物件的三組具體種類的等價類。注意一個條件一定能合併三組等價類，因為這三個等價類是一個關係集合的三個具體種類表現，同樣的一個等價類出現一定有其餘兩個等價類，且他們種類剛好補全所有情況。比如， \([a] = [b]\) 出現則一定有 \([a+n] = [b+n]\) 和 \([a+2n] = [b +2n]\)，因為他們是一個同一個相對關係（同類）的三個具體表現。

另一方面，對於 \(a\) 吃 \(b\) 的條件，如果它們已經在一個關係集合（已有相對關係），則它們之間一定產生了三個等價類，而如果這些等價類剛好是 \([a] = [b]\) 或者 \([a] = [b+2n]\) ，即表達 \(a\) 與 \(b\) 同類或者 \(a\) 的天敵是 \(b\) 就很容易判斷出已知條件與給出的這個條件矛盾。

因此，擴充套件域並查集能夠維護元素不同種類之間同時出現的集合，即等價類，容易直接判斷出條件是否矛盾。但弊端也很明顯，只適合檢驗某個條件相對關係是否滿足現有關係，而不能直接列舉出元素的相對關係，因為擴充套件域並查集只儲存了元素具體種類的等價關係，而沒有完整記錄元素在關係集合中的相對關係，導致等價類之間是割裂的，沒有直接相關性的。比如我想要知道動物 \(a\) 和 動物 \(b\) 的相對關係，就得先拿 \(a\) 的某個種類所在的等價類集合作為一個基準集合，再列舉 \(b\) 的所有種類(\(A,B,C\))是否處在這個基準集合，如果有關係則有且僅有一個具體種類處在基準集合進而判斷其相對關係，而都沒有處在基準集合說明 \(a\) 和 \(b\) 尚未建立關係。這個過程帶權並查集能在合併和查詢過程中直接實現，因此如果題目要求並不是檢驗條件矛盾這麼簡單的話，比如要求得知 \(a\) 和 \(b\) 的相對關係用以後續解題，那帶權並查集會更加合適。

時間複雜度 \(O(k\log n + n)\)

空間複雜度 \(O(n)\) ，實際上是三倍空間

程式碼

方法一

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int x = 0, f = 1;char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1;c = getchar(); }///整數符號
    while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48);c = getchar(); }///挪位加數
    return x * f;
}

int fa[50007], dist[50007];

int find(int x) {
    if (fa[x] != x) {
        int pre = fa[x];
        fa[x] = find(pre);
        dist[x] = (dist[x] + dist[pre]) % 3;
    }
    return fa[x];
}

bool merge(int x, int y, int op) {
    int rx = find(x);
    int ry = find(y);
    int delta = (dist[x] - dist[y] + 3) % 3;
    if (rx == ry) return delta == op;
    fa[rx] = ry;
    dist[rx] = (op - delta + 3) % 3;
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n = read(), k = read();
    for (int i = 1;i <= n;i++) fa[i] = i;
    int ans = 0;
    while (k--) {
        int op = read(), x = read(), y = read();
        op--;
        if (x > n || y > n) ans++;
        else if (!merge(x, y, op)) ans++;
    }
    cout << ans << '\n';
    return 0;
}

方法二

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int x = 0, f = 1;char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1;c = getchar(); }///整數符號
    while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48);c = getchar(); }///挪位加數
    return x * f;
}

int fa[150007];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n = read(), k = read();
    for (int i = 1;i <= 3 * n;i++) fa[i] = i;
    int ans = 0;
    while (k--) {
        int op = read(), x = read(), y = read();
        if (x > n || y > n)ans++;
        else if (op == 1) {
            if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) ans++;
            else merge(x, y), merge(x + n, y + n), merge(x + 2 * n, y + 2 * n);
        }
        else if (op == 2) {
            if (find(x) == find(y + 2 * n) || find(x) == find(y)) ans++;
            else merge(x, y + n), merge(x + n, y + 2 * n), merge(x + 2 * n, y);
        }
    }
    cout << ans << '\n';
    return 0;
}