Connected Components and Islands

1. What are Connected Components?

An undirected graph can be seen as a collection of one or more "connected components." A connected component is a subgraph where there is a path between any two vertices within that subgraph, and it is not connected to any other vertices in the supergraph.

Imagine a social network. A group of friends who are all interconnected would form one component. Another separate group of friends would form a second component. If no one from the first group knows anyone from the second, the graph of the social network has at least two connected components.

To get a more dynamic explanation of this idea, the following video provides a great introduction.

The Core Algorithm

As the video explained, the standard approach to deal with disconnected graphs or to count connected components is a simple but powerful extension to our standard traversal algorithms:

1. Initialize a visited array (or boolean array) for all vertices, marking them as false.
2. Initialize a counter for components to 0.
3. Iterate through all the vertices from 0 to V-1.
4. For each vertex i, check if it has been visited.
   • If visited[i] is false, it means we have found a new, unexplored component.
   • Increment the component counter.
   • Start a graph traversal (either DFS or BFS) from vertex i. This traversal will visit every node in the current component and mark them as true in the visited array.
5. After the loop finishes, the counter will hold the total number of connected components.

This pattern ensures that we start a new traversal for each component, and each traversal completely explores its own component before the main loop moves on to find the next one.

2. Problem: Number of Provinces

Let's apply this pattern to a classic problem, often called "Number of Provinces" or "Number of Connected Components." You're given a graph (often as an adjacency matrix or list) and asked to find the number of separate, connected groups of cities (provinces).

The following video provides an excellent walkthrough of this exact problem.

Java Implementation

Here's a clean Java implementation based on the logic from the video. This uses an adjacency list representation, which is standard for competitive programming and interviews.

import java.util.ArrayList;

public class NumberOfProvinces {

    public static int findNumOfProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        int provinceCount = 0;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                // Found a new component, so increment count and start a traversal
                provinceCount++;
                dfs(i, adj, visited);
            }
        }
        return provinceCount;
    }

    private static void dfs(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited);
            }
        }
    }

    public static void main(String[] args) {
        // Example with 2 provinces: {0, 1, 2} and {3, 4}
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Component 1
        adj.get(0).add(1);
        adj.get(1).add(0);
        adj.get(1).add(2);
        adj.get(2).add(1);

        // Component 2
        adj.get(3).add(4);
        adj.get(4).add(3);

        System.out.println("Number of provinces: " + findNumOfProvinces(adj, V)); // Output: 2
    }
}

You could just as easily use BFS instead of DFS for the traversal part. The overall structure of the main findNumOfProvinces function would remain identical.

3. Problem: Number of Islands

This is one of the most famous and common graph problems asked in interviews. You are given a 2D grid where '1' represents land and '0' represents water. Your task is to count the number of islands. An island is a group of connected '1's (horizontally or vertically).

This problem might not look like a graph problem at first, but it is! You can think of the grid as an implicit graph:

• Each cell (r, c) is a node.
• An edge exists between two nodes (cells) if they are adjacent (up, down, left, or right) and both contain '1'.

With this perspective, "counting the number of islands" is exactly the same as "counting the number of connected components." We can use the same pattern as before.

Algorithm for Number of Islands

1. Initialize islandCount to 0.
2. Iterate through every cell (r, c) of the grid.
3. If grid[r][c] is '1':
   • We've found the start of a new island, so increment islandCount.
   • Call a traversal function (like dfs(r, c)) to find and mark all parts of this island.
4. The dfs(r, c) function does the following:
   • Base Case / Boundary Check: If the cell is out of bounds or is water ('0'), return immediately.
   • Mark as visited: Change grid[r][c] from '1' to '0'. This "sinks" the land and prevents us from ever recounting it.
   • Explore Neighbors: Recursively call dfs for all four adjacent cells (up, down, left, right).

Here is the Java code, which you also saw in the article:

public class NumberOfIslands {

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int islandCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islandCount++;
                    dfs(grid, r, c);
                }
            }
        }
        return islandCount;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Boundary checks and water check
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
            return;
        }

        // Mark current cell as visited by "sinking" it
        grid[r][c] = '0';

        // Explore 4-directionally
        dfs(grid, r + 1, c); // down
        dfs(grid, r - 1, c); // up
        dfs(grid, r, c + 1); // right
        dfs(grid, r, c - 1); // left
    }
}

This is a very elegant and efficient solution that modifies the input grid to keep track of visited cells, saving space. However, as the AlgoMonster article points out, in an interview, it's wise to ask if modifying the input is acceptable. If not, you would use an auxiliary boolean[][] visited grid.

Conclusion

Today you learned a powerful and generalizable pattern for handling disconnected graphs and grid-based connectivity problems. This is a crucial skill for any programmer, especially for acing technical interviews.

Key Takeaways:

• A connected component is a subgraph where all vertices are reachable from each other.
• The general algorithm to count components involves iterating through all vertices and launching a traversal (DFS or BFS) from any unvisited vertex, incrementing a counter each time.
• The "Number of Islands" problem is a classic application of finding connected components on a 2D grid, where the grid itself acts as an implicit graph.
• Using a visited array (or modifying the input grid) is essential to ensure each component is counted exactly once.
• The overall time complexity for these problems is O(V + E) for an explicit graph (or O(rows * cols) for a grid), as each node and edge is visited a constant number of times across all traversal calls.

Preview of the Next Lesson:
While DFS/BFS are great for finding components, some problems require you to dynamically merge components or quickly check if two nodes belong to the same component. For this, we'll learn about a specialized and highly efficient data structure called Disjoint Set Union (DSU), also known as Union-Find. It's a cornerstone of many advanced graph algorithms.