Leetcode: Number of Connected Components in Undirected Graph

 This question is asked at both Amazon and Facebook and proceeds as follows:

You have a graph of n nodes, and you are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi inside of the graph. So we want to see how many connected graphs are in a diagram. The first diagram will have 2 connections, whereas the second graph will only have 1 connection.

If we run DFS vertices will be visited until we have no other verfices left to visit. The number of times we start DFS will be the number of connected components. Here's how we would approach solving this issue:

1. First, we want to create an adjacency list such that adj[v] contains the adjacent vertices of vertex v. We initialize a hashmap or array, called visited, to keep track of the visited vertices. WE define a counter video to 0 and have DFS. Everytime a DFS starts, increment the counter by 1 and the counter will contain the number of components in the graph. We can have an array for graph, or arraylist, if you are talking about the adjacency lists. Here's the code:

class Solution {

    private void dfs(List<Integer>[] adjList, int[] visited, int startNode) {

            visited[startNode] = 1;

            for(int i = 0; i < adjList[startNode].size(); i++) {    

                if(visited[adjList[startNode].get(i)] == 0 {

                    dfs(adjList, visited, adjList[startNode].get(i));

                }

            }

    }

    public int countComponents(int n, int[][] edges) {

        int components = 0;

        int[] visited = new int[n];

        List<Integer>[] adjList = new ArrayList[n];

        for(int i = 0; i < n; i++) {

            adjList[i] = new ArrayList<Integer>();

        }

        for(int i = 0; i < edges.length; i++) {

            adjList[edges[i][0]].add(edges[i][1]);

            adjList[edges[i][1]].add(edges[i][0]);

        }

        for(int i = 0; i < n; i++) {

            if(visited[i] == 0) {

                components++;

                dfs(adjList, visited, i);

            }

        }

        return components; 

    }

}