DSU Problem Why Wrong

Revision en1, by alirezaopmc, 2020-04-21 14:45:38

I was coding for 217A - Ice Skating but I got wrong answer on test 12, can anyone help me out with debugging this code?

Idea: bipartite graph (Union x and y for every point, xs are from 0 to 999 and ys are from 1000 to 1999) What I am doing is subtracting those components with size equal to one that from 2000. The remaining number is equal to the number of components.

    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    class DSU {
     
    public:
        int size;
        int components;
        vector<int> component_size;
        vector<int> id;
     
        DSU(int size) {
            this->size = size;
            this->components = size;
            this->component_size.resize(size, 1);
            this->id.resize(size);
            for(int i = 0; i < size; i++) {
                id[i] = i;
            }
        }
     
        int getSize() {
            return this->size;
        }
     
        int Find(int a) {
            int root = a;
     
            while(root != id[root]) {
                root = id[root];
            }
     
            while(a != root) {
                id[a] = root;
                a = id[a];
            }
     
            return root;
        }
     
        int Union(int a, int b) {
            int root_a = Find(a);
            int root_b = Find(b);
     
            if(root_a == root_b) {
                return root_a;
            } else {
                if (component_size[root_a] > component_size[root_b]) {
                    component_size[root_a] += component_size[id[root_b]];
                    components--;
                    return id[root_b] = root_a;
                } else {
                    component_size[root_b] += component_size[id[root_a]];
                    components--;
                    return id[root_a] = root_b;
                }
            }
        }
     
        void Show() {
            for(int i=0; i<size; i++) {
                cout << i << ' ' << id[i] << endl;
            }
            cout << endl;
            for(int i=0; i<size; i++) {
                cout << i << ' ' << component_size[Find(i)] << endl;
            }
        }
     
    };
     
    void test();
     
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t;
        t = 1;
    //    cin >> t;
        while(t--) {
            test();
            cout << endl;
        }
    }
     
    void test() {
        int n;
        cin >> n;
        DSU dsu(2000);
        for(int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            dsu.Union(x - 1, 1000 + y - 1);
        }
        int ans = 2000;
        for(int i=0; i<2000; i++) {
            dsu.Find(i);
            if(dsu.component_size[i] == 1) {
                ans--;
            }
        }
        cout << ans - 1 << endl;
    }
Tags #dsu, #bug, #wrong_answer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English alirezaopmc 2020-04-21 14:45:38 3039 Initial revision (published)