323. Number of Connected Components in an Undirected Graph

Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:


 0          3
 |          |
 1 --- 2    4


Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.


Example 2:


 0           4
 |           |
 1 --- 2 --- 3


Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

public class Solution {
  public int countComponents(int n, int[][] edges) {
        Map<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < n; i ++) {
            map.put(i, new Node(i));
        }

        for(int i = 0; i < edges.length; i ++) {
            int x = edges[i][0];
            int y = edges[i][1];

            Node nodeX = map.get(x);
            Node nodeY = map.get(y);
            Edge edge = new Edge(nodeX, nodeY);

            nodeX.edges.add(edge);
            nodeY.edges.add(edge);
        }

        int count = 0;
        Map<Node, Boolean> visit = new HashMap<>();
        for(Integer key:map.keySet()) {
            Node cur = map.get(key);
            if (!visit.containsKey(cur)) {
                count ++;
                dfs(cur, visit);
            }
        }

        return count;

    }

    private void dfs(Node node, Map<Node, Boolean> map) {
        map.put(node, true);

        for(Edge edge: node.edges) {
            Node next = edge.other(node);
            if (!map.containsKey(next)) {
                dfs(next, map);
            }
        }
    }

    private class Edge {
        Node m;
        Node n;

        public Edge(Node m, Node n) {
            this.m = m;
            this.n = n;
        }

        public Node other(Node c) {
            if (m == c) {
                return n;
            } else {
                return m;
            }
        }

    }

    private class Node {
        int val;
        List<Edge> edges;

        public Node(int val) {
            this.val = val;
            edges = new ArrayList<>();
        }
    }
}