Lintcode 431: Connected Component in Undirected Graph

431. Connected Component in Undirected Graph

中文English

Find connected component in undirected graph.

Each node in the graph contains a label and a list of its neighbors.

(A connected 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.)

You need return a list of label set.

Example

Example 1:

Input: {1,2,4#2,1,4#3,5#4,1,2#5,3}
Output: [[1,2,4],[3,5]]
Explanation:

  1------2  3
   \     |  | 
    \    |  |
     \   |  |
      \  |  |
        4   5

Example 2:

Input: {1,2#2,1}
Output: [[1,2]]
Explanation:

  1--2

Clarification

Learn more about representation of graphs

Notice

Nodes in a connected component should sort by label in ascending order. Different connected components can be in any order.

Code (Java):

/**
 * 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(List<UndirectedGraphNode> nodes) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return ans;
        }
        
        Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList = new HashMap<>();
        for (UndirectedGraphNode node : nodes) {
            adjList.put(node, node.neighbors);
        }
        
        Set<UndirectedGraphNode> visited = new HashSet<>();
        
        for (UndirectedGraphNode node : nodes) {
            if (!visited.contains(node)) {
                List<Integer> cc = bfs(adjList, node, visited);
                ans.add(cc);
            }
        }
        
        return ans;
    }
    
    private List<Integer> bfs(Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList, UndirectedGraphNode node, Set<UndirectedGraphNode> visited) {
        List<Integer> ans = new ArrayList<>();
        
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        visited.add(node);
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode v = queue.poll();
            ans.add(v.label);
            
            for (UndirectedGraphNode neighbor : adjList.get(v)) {
                if (visited.contains(neighbor)) {
                    continue;
                }
                
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
        
        Collections.sort(ans);
        
        return ans;
    }
}