Submission

Score: 100

User: koon

Problemset: Tech Sprites

Language: cpp

Time: 0.575 second

Submitted On: 2026-04-23 20:19:38

#include <bits/stdc++.h>
using namespace std;

struct node {
    int s, a, b;

    bool operator<(const node &o) const {
        if (a == o.a) return b < o.b;
        return a < o.a;
    }
};

struct DSU {
    vector<int> rnk, prev;

    void init(int n) {
        rnk.assign(n+1, 1);
        prev.assign(n+1, -1);
    }

    int find_prev(int u) {
        if (prev[u] == -1) return u;
        return prev[u] = find_prev(prev[u]);
    }

    void union_node(int a, int b, bool fix) {
        a = find_prev(a);
        b = find_prev(b);
        if (a == b) return;

        if (fix) {
            prev[b] = a;
            return;
        }

        if (rnk[a] > rnk[b]) {
            prev[b] = a;
            rnk[a] += rnk[b];
        } else {
            prev[a] = b;
            rnk[b] += rnk[a];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;

    vector<node> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i].a >> vec[i].b;
        vec[i].s = i+1;
    }

    sort(vec.begin(), vec.end());

    DSU tree;
    tree.init(n);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        tree.union_node(a, b, false);
    }

    stack<int> st;
    vector<bool> in_stack(n+1, false);
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        int x = tree.find_prev(vec[i].s);

        if (!st.empty() && x == st.top()) continue;

        if (!in_stack[x]) {
            st.push(x);
            in_stack[x] = true;
        } else {
            while (st.top() != x) {
                int y = st.top(); st.pop();
                in_stack[y] = false;
                tree.union_node(x, y, true);
                cnt++;
            }
        }
    }

    cout << cnt;
    return 0;
}

//01.29.47
//เขียน DUS ผิด