Video Explanation | Union Find and DFS | Including Similar Problems
Approach\n\nhttps://youtu.be/76eTRuAszl0\n\n# Similar Problems\n- 463. Island Perimeter\n- 657. Robot Return to Origin\n- 200. Number of Islands\n- Number of Is
# Approach\n\nhttps://youtu.be/76eTRuAszl0\n\n# Similar Problems\n- [463. Island Perimeter](https://leetcode.com/problems/island-perimeter/)\n- [657. Robot Return to Origin](https://leetcode.com/problems/robot-return-to-origin/)\n- [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)\n- [Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)\n- [2316. Count Unreachable Pairs of Nodes in an Undirected Graph](https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/)\n- [Number of Distinct Islands](https://leetcode.com/problems/number-of-distinct-islands/)\n- [Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)\n- [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)\n- [2658. Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/)\n- [994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)\n- [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)\n- [529. Minesweeper](https://leetcode.com/problems/minesweeper/)\n- [1376. Time Needed to Inform All Employees](https://leetcode.com/problems/time-needed-to-inform-all-employees/)\n- [2101. Detonate the Maximum Bombs](https://leetcode.com/problems/detonate-the-maximum-bombs/)\n\n# Union Find\n``` Java []\nclass Solution {\n    int[] par;\n    int[] rank;\n    public int findCircleNum(int[][] isConnected) {\n        int n = isConnected.length;\n        par = new int[n];\n        rank = new int[n];\n        for(int i=0; i<n; i++){\n            // make each node it\'s own parent..\n            par[i] = i;            \n            // rank is the number of nodes it points to..\n            rank[i] = 1;\n        }\n        int groups = n;\n        for(int i=0; i<n; i++){\n            for(int j=0; j<n; j++){\n                if(isConnected[i][j]==1)\n                    // for each edge check if it is in a union\n                    // or add it to an existing union set\n                    // if added to an existing union set,\n                    // returns 1 which is decremented from res...\n                    // finally, the number of unions will be\n                    // res - the count of edges for which we added to previous union set.\n                    groups -= union_find(i, j);\n            }\n        }\n        return groups;\n    }\n    \n    int union_find(int n1, int n2){\n        int p1 = find(n1);\n        int p2 = find(n2);\n        // the nodes that are already in a union set will have same parent\n        if(p1==p2)\n            return 0;\n        \n        // higher ranked node will be the parent of the lower rank node.. \n        if(rank[p1]>rank[p2]){\n            // change the parent of lower rank node\n            par[p2] = p1;\n            // increase the rank up to lower ranked node.. \n            rank[p1] += rank[p2];\n        }\n        else{\n            par[p1] = p2;\n            rank[p2] += rank[p1];\n        }\n        return 1;\n    }\n    \n    int find(int x){        \n        // find the top most parent of the current node\n        // top most parent will have itself as it\'s parent\n        while(par[x]!=x){\n            // basically it will be like a linkedlist..\n            // optimization is to first check the grand parent of the node.\n            par[x] = par[par[x]];\n            x = par[x];\n        }\n        return x;\n    }\n}\n```\n# Complexity\n- Time complexity: $$O(N^2)$$.\n   - $$O(N^2)$$ time to iterate over all the values in **isConnected** matrix.\n   - In worst case, the find operation takes $$O(N)$$ time. It takes $$O(1)$$ per operation and takes $$O(e)$$ time for all the $$e$$ edges.\n\n- Space complexity: $$O(N)$$.\nWe are using the parent and rank arrays, both of which require $$O(N)$$ space each.\n\n\n# DFS\n``` Java []\npublic class Solution {\n    int n;\n    public void dfs(int[][] isConnected, boolean[] visited, int i) {\n        for (int j=0; j<n; j++) {\n            if (isConnected[i][j] == 1 && !visited[j]) {\n                visited[j] = true;\n                dfs(isConnected, visited, j);\n            }\n        }\n    }\n    public int findCircleNum(int[][] isConnected) {\n        n = isConnected.length;\n        boolean[] visited = new boolean[n];\n        int groups = 0;\n        for (int i=0; i<n; i++) {\n            if (!visited[i]) {\n                dfs(isConnected, visited, i);\n                groups++;\n            }\n        }\n        return groups;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    void dfs(int node, vector<vector<int>>& isConnected, vector<bool>& visited) {\n        visited[node] = true;\n        for (int i = 0; i < isConnected.size(); i++) {\n            if (isConnected[node][i] && !visited[i]) {\n                dfs(i, isConnected, visited);\n            }\n        }\n    }\n\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int n = isConnected.size();\n        int groups = 0;\n        vector<bool> visited(n);\n\n        for (int i = 0; i < n; i++) {\n            if (!visited[i]) {\n                groups++;\n                dfs(i, isConnected, visited);\n            }\n        }\n\n        return groups;\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/db1c31ad-2de7-49be-baf3-59e55bb260c9_1685998592.383325.png)\n\n# Complexity\n- Time complexity: $$O(N^2)$$.\nIterating the matrix takes $$O(N^2)$$ time.\n\n- Space complexity: $$O(N)$$.\nThe **visited** array takes $$O(N)$$ space.\nThe recursion call stack used by dfs can have no more than $$n$$ elements in the worst-case scenario. It would take up $$O(N)$$ space in that case.\n
['Depth-First Search', 'Union Find', 'C++', 'Java']