Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)
Given graph:
A------B C \ | | \ | | \ | | \ | | D E Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}
/** * Definition for Undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) { // Write your code here List<List<Integer>> result = new ArrayList<List<Integer>> (); List<Integer> list = new ArrayList<Integer>(); Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>(); for(UndirectedGraphNode node:nodes){ if(!visited.contains(node)){ dfs(node,visited,list); Collections.sort(list); result.add(new ArrayList<Integer>(list)); list.clear(); } } return result; } public void dfs(UndirectedGraphNode node,Set<UndirectedGraphNode> visited, List<Integer> list){ visited.add(node); list.add(node.label); for(UndirectedGraphNode n : node.neighbors){ if(!visited.contains(n)) dfs(n,visited,list); } } }
public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) { // Write your code here List<List<Integer>> result = new ArrayList<List<Integer>> (); List<Integer> list = new ArrayList<Integer>(); Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>(); for(UndirectedGraphNode node: nodes){ if(!visited.contains(node)){ list.clear(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); queue.add(node); visited.add(node); list.add(node.label); while(!queue.isEmpty()){ UndirectedGraphNode current = queue.poll(); for(UndirectedGraphNode n:current.neighbors){ if(!visited.contains(n)){ queue.offer(n); list.add(n.label); visited.add(n); } } } Collections.sort(list); result.add(new ArrayList<Integer>(list)); } } return result; }