Intersected Rectangles, C++ (gcc)

Intersected Rectangles

/*31 Number of Intersected Rectangles
Given lots of rectangles, output how many of them intersect.
=> actually how many subsets they can be divided. 
*/
/* In Uion-Find's parents vector, each subset has only one parent root. Each element denotes the current node's parent node index, or parent node in short. 
   You can look for the parent root by this parent index, until you find a -1, which means the current node is the parent root. 
   When a node's parent's root is the different from the other node, meaning these two nodes are not within the same subset. Otherwise, they are in the same subset. 
   // 'find' func is to find the parent root; 
   // 'union' func is to union two subset, by setting parents[root1] = root2, or parents[root2] = root1; 
*/

#include <iostream>
#include <vector>
#include <set>
using namespace std ;

class Rect{
public:
    bool isIntersected(vector<int>& r1, vector<int>& r2){
        // r1[x1,y1, x2,y2]
        // r2[x1,y1, x2,y2]
        bool separated = r1[0] > r2[2] || r1[1] > r2[3] || r2[0] > r1[2] || r2[1] > r1[3];
        return !separated;
    }

int getSubset(vector<vector<int>>& rect) {
        int n = rect.size();
        int res = n;
        if(n<=1) return n;
        vector<int> parent(n, -1);  // 
        for(int i =0; i<n; i++){
            for(int j=0; j<n; j++){
                if(isIntersected(rect[i], rect[j])){
                    int root1 = find(parent, i);
                    int root2 = find(parent, j);
                    if(root1 != root2){
                        parent[root1] = root2;
                        res--;
                    }
                }
            }
        }
        return res;
    }

int find(vector<int>& v, int i) {
        while(v[i] != -1  ) i = v[i];
        return i;
    }

};

int main() {
    vector<vector<int>> rect = {
            {2,2, 4, 4}, {2,2, 4, 4},  {1,1, 3, 3},
            {11,11, 12,12}

};
    Rect r;
    cout << r.getSubset(rect) << endl;

return 0;
}


run \| edit \| history \| help	0