[Java] DFS Connected Components Solution | Union Find Solution
Solution 1:  DFS connected components\n\nIterate the matrix and paint different components with different colors and store the size of each component.\nIterate 
Solution 1:  DFS connected components\n\nIterate the matrix and paint different components with different colors and store the size of each component.\nIterate the matrix again whenever you find zero try to connect them under single component and store the maximum size.\n\nNote:\n 1. The colors shoud start from 2 since 0 and 1 are already in the matrix.\n 2. Set is used in second iteration because colors are unique for every component. If 2 neighbors have same color they are part of the same component. Hence to prevent repetition set is used. \n\nTime Complexity: 0(n^2) effectively\n\n```\nclass Solution {\n    \n    int [][]dirs={{0,1},{1,0},{0,-1},{-1,0}};\n    Map<Integer,Integer> component=new HashMap<>();\n    \n    void paint(int [][]grid,int i,int j,int color) {\n        if(i<0 || j<0 || i>=grid.length || j>=grid.length || grid[i][j]!=1) return;\n        grid[i][j]=color;\n        component.put(color,component.getOrDefault(color,0)+1);\n        for(int []dir:dirs)\n            paint(grid,i+dir[0],j+dir[1],color);\n    }\n    \n    public int largestIsland(int [][]grid) {\n        int n=grid.length,ans=0,color=2;\n        \n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]==0) continue;\n                paint(grid,i,j,color);\n                if(component.containsKey(color))\n                    ans=Math.max(ans,component.get(color));\n                color++;\n            }\n        }\n        \n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]!=0) continue;\n                Set<Integer> neigh=new HashSet<>();\n                for(int []dir:dirs) {\n                    int x=i+dir[0],y=j+dir[1];\n                    if(x<0 || y<0 || x>=n || y>=n || grid[x][y]==0) continue;\n                    neigh.add(grid[x][y]);\n                }\n                \n                int size=1;\n                for(int s:neigh)\n                    size+=component.get(s);\n                \n                ans=Math.max(ans,size);\n            }\n        }\n        return ans;\n    }\n}\n```\n\t\nSolution 2: Union Find Solution\n\t\nThis solution is same as DFS solution. Only difference is instead of colors we use Union Find here.\nIterate the matrix and wherever you find 1 add it to the Union find and update ans with maximum size.\nIterate the matrix. This time check for 0s. Whenver you find a zero get the component sizes from the neighbors and update the ans with maximum size.\n\nTime Complexity: 0(n^2) effectively\n\n```\nclass Solution {\n\t UnionFind uf;\n    public int largestIsland(int[][] grid) {\n        int n=grid.length;\n        uf=new UnionFind(n*n);\n        int ans=0;\n        \n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]==0) continue;\n                int curr=i*n+j;\n                \n                uf.add(curr);\n                for(int neigh:neighbors(grid,i,j))\n                    uf.union(curr,neigh);\n                \n                int p=uf.find(curr);\n                ans=Math.max(ans,uf.size[p]);\n            }\n        }\n        \n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]==1) continue;\n                Set<Integer> neighParents=new HashSet<>();\n                for(int neigh: neighbors(grid,i,j))\n                    neighParents.add(uf.find(neigh));\n                \n                int size=1;\n                for(int s:neighParents)\n                    size+=uf.size[s];\n                ans=Math.max(ans,size);\n            }\n        }\n        return ans;\n\t\t}\n    \n    int [][]dirs={{0,1},{1,0},{0,-1},{-1,0}};\n    \n    List<Integer> neighbors(int [][]grid,int i,int j) {\n        int n=grid.length;\n        List<Integer> list=new ArrayList<>();\n        for(int []dir:dirs) {\n            int x=i+dir[0],y=j+dir[1];\n            if(x<0 || y<0 || x>=n || y>=n || !uf.contains(x*n+y))\n                continue;\n            list.add(x*n+y);\n        }\n        return list;\n    }\n    \n    class UnionFind {\n        int []parent,size;\n        \n        UnionFind(int n) {\n            parent=new int[n];\n            Arrays.fill(parent,-1);\n            size=new int[n];\n        }\n        \n        boolean contains(int u) {\n            return parent[u]>=0;\n        }\n        \n        void add(int u) {\n            if(contains(u)) return;\n            parent[u]=u;\n            size[u]=1;\n        }\n        \n        int find(int u) {\n            if(parent[u]==u) return u;\n            parent[u]=find(parent[u]); //path compression\n            return parent[u];\n        }\n        \n        boolean union(int u,int v) {\n            int pu=find(u),pv=find(v);\n            if(pu==pv) return false;\n            if(size[pu]<=size[pv]) { //merge smaller component\n                parent[pu]=pv;\n                size[pv]+=size[pu];\n            }\n            else {\n                parent[pv]=pu;\n                size[pu]+=size[pv];\n            }\n            return true;\n        }\n    }\n}\n
['Depth-First Search', 'Union Find', 'Java']