3 Solutions | BFS + DFS + DSU | ☑️Path Compression + Rank & Size Method✅ | 🔥Clean CPP Code🔥
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣IntuitionHi There! Take A Look At The Code You'll Get It.
Still Have Doubts! Feel Free To Comment, I'll Definitely Reply!ApproachAll Accepte
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
***Hi There! Take A Look At The Code You'll Get It.
Still Have Doubts! Feel Free To Comment, I'll Definitely Reply!***

# Approach
<!-- Describe your approach to solving the problem. -->
***All Accepted : 
-> Using BFS & DFS
-> Using DSU - Union Find (Path Compression + Rank & Size Method)***

# Complexity
- ***Time complexity: Mentioned with the code***
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity: Mentioned with the code***
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
**Approach 1 : Using BFS & DFS**
```
class CountComponentsUsingBFSOrDFS {
private:
    vector<vector<int>> adjList;

    void BFS(int node, vector<bool>& visited) {
        queue<int> q;
        q.push(node);

        visited[node] = true;

        while(!q.empty()) {
            node = q.front(); q.pop();

            for(int neighbor : adjList[node]) {
                if(!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }

    void DFS(int node, vector<bool>& visited) {
        visited[node] = true;

        for(int neighbor : adjList[node])
            if(!visited[neighbor])
                DFS(neighbor, visited);
    }

private:
    int intersect(const unordered_set<int>& nums1, const unordered_set<int>& nums2) {
        int commonElements = 0;
        for(int num : nums1) commonElements += nums2.count(num);
        return commonElements;
    }

public:
    // O(N*M*M) & O(N*M) : Where N = properties.size(), M = properties[i].size().
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int n = properties.size();
        adjList.resize(n);

        // Recreate the properties so that each properties[i] stores unique values
        vector<unordered_set<int>> grid(n); 
        for(int i = 0; i < n; ++i) 
            for(int num : properties[i])
                grid[i].insert(num);

        // Construct the graph
        for(int i = 0; i < n; ++i) 
            for(int j = i+1; j < n; ++j)
                if(intersect(grid[i], grid[j]) >= k)
                    adjList[i].push_back(j), 
                    adjList[j].push_back(i);

        // Visit all the components, count the result value
        vector<bool> visited(n);
        int countComponents = 0;
        for(int node = 0; node < n; ++node) 
            if(!visited[node])
                DFS(node, visited),
                countComponents++;

        return countComponents;
    }
};
```
**Approach 2 : Using DSU - Union Find (Path Compression + Rank & Size Method)**
```
class CountComponentsUsingDSU {
private:
    vector<int> rank, size, parent;
    
    int findRoot(int node) {
        if(parent[node] == node) 
            return node;
        return parent[node] = findRoot(parent[node]);
    }

    void unionBySize(int u, int v) {
        int root_u = findRoot(u);
        int root_v = findRoot(v);

        if(root_u == root_v)
            return;
        else if(size[root_u] < size[root_v])
            parent[root_u] = root_v, 
            size[root_v] += size[root_u];
        else 
            parent[root_v] = root_u, 
            size[root_u] += size[root_v];
    }

    void unionByRank(int u, int v) {
        int root_u = findRoot(u);
        int root_v = findRoot(v);

        if(root_u == root_v)
            return;
        else if(rank[root_u] < rank[root_v])
            parent[root_u] = root_v;
        else if(rank[root_v] < rank[root_u])
            parent[root_v] = root_u;
        else
            parent[root_v] = root_u, 
            rank[root_u]++;
    }

private:
    int intersect(const unordered_set<int>& nums1, const unordered_set<int>& nums2) {
        int commonElements = 0;
        for(int num : nums1) commonElements += nums2.count(num);
        return commonElements;
    }

public:
    // O(N*M*M) & O(N*M) : Where N = properties.size(), M = properties[i].size().
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int n = properties.size();

        // Initialize DSU buffers
        rank.resize(n);
        size.resize(n, 1);
        parent.resize(n, -1);
        for(int node = 0; node < n; ++node) 
            parent[node] = node;

        // Recreate the properties so that each properties[i] stores unique values
        vector<unordered_set<int>> grid(n);
        for(int i = 0; i < n; ++i) 
            for(int num : properties[i])        
                grid[i].insert(num);

        // Construct the graph edges
        vector<vector<int>> edges;
        for(int i = 0; i < n; ++i) 
            for(int j = i+1; j < n; ++j)
                if(intersect(grid[i], grid[j]) >= k)
                    edges.push_back({i, j});

        // Hit DSU, build the components
        for(auto& edge : edges) { 
            int u = edge[0];
            int v = edge[1];
            unionBySize(u, v);
        }

        // Mark root nodes of each component, count the result value
        vector<bool> isRootOfAnyComponent(n);
        int countComponents = 0;
        for(int node = 0; node < n; ++node)
            isRootOfAnyComponent[findRoot(node)] = true,
            countComponents += isRootOfAnyComponent[node];

        return countComponents;
    }
};
```
𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'Matrix', 'C++']