CONNECTED COMPONENTS TO UNDERSTAND | MUST DO | TRICKY | OA

https://practice.geeksforgeeks.org/contest/gfg-weekly-coding-contest-97/problems/#

Geek has grown a good garden with certain plants having their branches joined with each other. The number of plants in Geeks garden is N and the number of branches that are overtopped is M. A malicious guy wants to destroy the Gecko garden by sprinkling poison on the plants. The poison required to destroy a plant is given by an array arr. When a plant say x gets destroyed then all the plants with overtopping branches (directly or indirectly) and requiring less than or equat poison gets destroyed. Now calculate the minimum amount of poison he must buy to destroy the Geeks garden.

Example 1:
N = 5, M = 2
arr = [2, 3, 4, 5, 6]
overlapped = [ [1, 5],
               [3, 4]]
Output:
14
Explanation:
6 units of poison can destroy the first and the last plant, 3 units of poison can destroy the 2nd plant and 5 units of poison can destroy the 3rd and the 4th plant.

Example 2:
Input:
N = 4, M = 3
arr = [1, 2, 3, 4]
overlapped = [ [1, 2],
               [2, 3],
               [3, 4]]

Output:
4
Explanation:
Geek can ddestroy the 4th plant with 4 units of poison and since it overlaps with the 3rd plant it also gets destroyed. Now, when the third plant gets destroyed it also destroys the 2nd plant since it overlaps with third and requires less poison. Similarly upon destroying second plant will also destroy the first one.

--------------------------------------------------------------------------------------------------------------------

class Solution {
public:
    long destroyTheGarden(int n, int m, vector<int> &arr, vector<vector<int>> &overlapped) {
        long ans = 0;
        adj.resize(n + 1);
        for(int i = 0; i <= n; i++)
            adj[i] = vector<int>();
        for(int i = 0; i < m; i++){
            int x = overlapped[i][0];
            int y = overlapped[i][1];
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        vis.clear();
        for(int i = 1; i <= n; i++){
            if(!vis.count(i)){
                vis.insert(i);
                ans += dfs(i, arr);
            }
        }
        return ans;
    }

    int dfs(int node, vector<int> &arr) {
        int val = arr[node - 1];
        vis.insert(node);
        for(int ngr : adj[node]) {
            if(!vis.count(ngr)){
                val = max(val, dfs(ngr, arr));
            }
        }
        return val;
    }

private:
    set<int> vis;
    vector<vector<int>> adj;
};