alirezaopmc's blog

By alirezaopmc, history, 4 years ago, In English

I was coding for 217A - Катание на Коньках 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;
    }
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

See this case

case

When the 3rd line is processed, there are 2 components {x=1,y=1} and {x=2,y=2}. then these will be connected, component_size will be 2 and 4, and your output will be 1.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thankyou for your great help. I

    was wrong on computing the components.

    I fixed my code with changing my last loop:

    for (int i = 0; i < 2000; i++) {
            int root = dsu.Find(i);
            if (root != i && c[root]) {
                c[root] = false;
                ans++;
            }
        }
    

    The main idea is executing Find function for every unchecked element for path compression.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow.. great catch .,.. this really helped me understand the topic better..!!