We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The general idea for my solution is to convert the gb input they gave into a (psuedo) AdjacencyList, then DFS through every vertex I have not visited. As I DFS, I keep track of a counter that counts how many vertices I visit during that traversal. Once I finish the DFS, I update my smallest and largest variables, reset counter, DFS the next unvisited vertex, and repeat the process.
Once I've visited every vertex, I know I've fully traveresed the graph (and all potential sub-graphs) so I return the smallest and largest as an int[].
privatestaticHashMap<Integer,ArrayList<Integer>>graph;// class-scoped graph variableprivatestaticintcurCount;// class scoped vertex counter for current DFS traversalstaticint[]componentsInGraph(int[][]gb){graph=buildGraph(gb);// Build the graphHashMap<Integer,Boolean>visited=newHashMap<Integer,Boolean>();// Similar reasoning for a HashMap here follows reasoning for buildGraph methodintshortest=Integer.MAX_VALUE;intlongest=0;// Note that our graph may be a disconnected graph// Consider vertices [1, 4], [1, 5], [3, 6], [3, 7], [3, 8]for(Integeri:graph.keySet()){// Go through every vertex in the graphif(visited.get(i)==null){// If that vertex has not yet been visitedcurCount=0;// Reset traversal counter to 0DFSSearch(i,visited);// Traverse it// After traversal, curCount contains the number of vertices in that graph. This may or may not be the only graphlongest=Math.max(curCount,longest);shortest=Math.min(curCount,shortest);}}int[]ans={shortest,longest};returnans;}// Standard DFS traversal, except on each recursive call, curCount is incrementedprivatestaticvoidDFSSearch(intcurVal,HashMap<Integer,Boolean>visited){visited.put(curVal,true);curCount++;// Each recursive call means we go one vertex deeper into the graphfor(Integeri:graph.get(curVal)){// Go through all vertices associated to that vertexif(visited.get(i)==null){// If that vertex has not yet been visitedDFSSearch(i,visited);// Recursively burrow down to that vertex}}}// Converts given 2D array into a graph// Instead of typical adecency list (aka a list of lists), I have a mapping of Vertex to all of its connected Vertices// Since we aren't guarenteed that all edge values will be continious// (ie. we can't guarentee we'll get [1, 4], [2, 5], [3, 6] -- instead we may get [2, 4], [2, 5], [2, 6], notice that 1 and 3 are not present)privatestaticHashMap<Integer,ArrayList<Integer>>buildGraph(int[][]gb){HashMap<Integer,ArrayList<Integer>>graph=newHashMap<Integer,ArrayList<Integer>>();for(int[]edge:gb){inte0=edge[0];inte1=edge[1];if(graph.get(e0)==null){graph.put(e0,newArrayList<Integer>());}if(graph.get(e1)==null){graph.put(e1,newArrayList<Integer>());}graph.get(e0).add(e1);graph.get(e1).add(e0);}returngraph;}
Components in a graph
You are viewing a single comment's thread. Return to all comments →
Here's a Java 8 solution.
The general idea for my solution is to convert the
gb
input they gave into a (psuedo) AdjacencyList, then DFS through every vertex I have not visited. As I DFS, I keep track of a counter that counts how many vertices I visit during that traversal. Once I finish the DFS, I update mysmallest
andlargest
variables, reset counter, DFS the next unvisited vertex, and repeat the process.Once I've visited every vertex, I know I've fully traveresed the graph (and all potential sub-graphs) so I return the
smallest
andlargest
as anint[]
.