Union checking set

1. Common operations and optimization

• Merge two sets
• Query the ancestor node of an element
• In the process of query, you can do path compression

2. Use scenarios

It is often used in topics with transitive properties , And the transmission is bidirectional , That is, it can be understood as undirected graph relationship .

3. Example

3.1 Understanding of topic meaning

Use prefixes and ideas : Si Before presentation i In number 1 Number of S[l~r] There are odd numbers of 1 de Equivalent to S[r] - S[l-1] It's odd Equivalent to S[r] And S[l-1] It's different in parity ; The same can be inferred , S[l-r] There are even numbers of 1 Equivalent to S[r] And S[l-1] The parity of is the same .

Therefore, the meaning of the question can be simplified as : Given two and the parity between them , Judge whether there is contradiction according to the given conditions .

3.2 Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 20004;

int fa[N];  //  And look up the array 
int d[N];  //  Maintain the distance to the root node 
unordered_map<int, int> s;  //  For discretizing points 

int n, m;

int find(int x) {
    if(x != fa[x]) {
        int root = find(fa[x]);
        //  In the mold  2  Under the state of ,  Addition is equivalent to   Exclusive or operation 
        d[x] ^= d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

int get(int x) {
    if(s.count(x) == 0) s[x] = ++n;
    return s[x];
}

int main() {
    cin >> n >> m;
    n = 0;
    
    //  And search set initialization 
    for(int i = 0; i < N; i++) fa[i] = i;
    
    int ans = m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        string op;
        cin >> a >> b >> op;
        
        //  Use similar prefixes and ideas ,  therefore  b  need  -1
        a = get(a - 1), b = get(b);
        int t = 0;
        if(op == "odd") t = 1;
        
        int pa = find(a), pb = find(b);
        if(pa == pb) {
            if((d[a] ^ d[b]) != t) {
                ans = i - 1;
                break;
            }
        } else {
            fa[pa] = pb;
            d[pa] = d[a] ^ d[b] ^ t;
        }
    }
    cout << ans;
    
    return 0;
}