The Number of Provinces problem is a foundational graph theory challenge that involves finding the number of connected components in an undirected graph. This problem helps build a solid understanding of graph traversal techniques like Depth-First Search (DFS), Breadth-First Search (BFS), and Union-Find. Let’s dive into the problem statement and its key concepts.
Understanding the Problem: Number of Provinces
You are given:
• A matrix isConnected, where:
• isConnected[i][j] = 1 means there’s a direct connection between city i and city j.
• isConnected[i][j] = 0 means there’s no direct connection.
• Each city is connected to itself, meaning isConnected[i][i] = 1.
Goal:
Determine the number of provinces (connected components) in the graph.
Key Points
1. Provinces:
• A province is a group of cities that are directly or indirectly connected.
• For example:
• If city A is connected to city B, and city B is connected to city C, then A, B, and C form a single province.
2. Graph Representation:
• The adjacency matrix isConnected represents an undirected graph, where:
• Rows and columns correspond to cities (nodes).
• A value of 1 at isConnected[i][j] indicates an edge between nodes i and j.
3. Connected Components:
• The task is equivalent to finding connected components in an undirected graph.
• Each connected component represents one province.
Approach: Depth-First Search (DFS)
Key Intuition
• Each city represents a node, and each direct connection (1 in the matrix) represents an undirected edge.
• DFS allows us to traverse all nodes connected to a given starting node. Once a connected component is fully traversed, we can count it as one province.
Steps to Solve with DFS
1. Track Visited Nodes:
• Use a boolean array visited to keep track of which cities have been processed.
2. Traverse the Graph:
• For each unvisited city, initiate a DFS to visit all directly and indirectly connected cities.
3. Count Provinces:
• Every time a DFS starts from an unvisited city, increment the province count.
public class NumberOfProvinces {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length; // Number of cities
boolean[] visited = new boolean[n]; // Track visited cities
int provinces = 0; // Count of provinces
// Iterate through each city
for (int i = 0; i < n; i++) {
if (!visited[i]) { // If city is unvisited, start a new DFS
dfs(isConnected, visited, i);
provinces++; // Increment province count
}
}
return provinces;
}
private void dfs(int[][] isConnected, boolean[] visited, int city) {
visited[city] = true; // Mark the city as visited
// Explore all connected cities
for (int neighbor = 0; neighbor < isConnected.length; neighbor++) {
if (isConnected[city][neighbor] == 1 && !visited[neighbor]) {
dfs(isConnected, visited, neighbor); // Recursively visit unvisited neighbors
}
}
}
}Approach: BFS
Steps to Solve with BFS
1. Initialize Variables:
• Use a boolean array visited[] to track whether a city has already been processed.
• Maintain a counter provinces to count the connected components.
2. Iterate Through Cities:
• For each city, if it hasn’t been visited, initiate a BFS traversal from that city.
• Mark all cities connected to it as visited.
3. Queue for BFS:
• Use a queue to process cities iteratively:
• Add the starting city to the queue.
• For each city in the queue, explore its unvisited neighbors and add them to the queue.
4. Count Provinces:
• Increment the provinces counter each time a BFS starts from an unvisited city.
import java.util.*;
public class NumberOfProvinces {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length; // Number of cities
boolean[] visited = new boolean[n]; // Track visited cities
int provinces = 0; // Count of provinces
// Iterate through each city
for (int i = 0; i < n; i++) {
if (!visited[i]) { // If city is unvisited, start a new BFS
bfs(isConnected, visited, i);
provinces++; // Increment province count
}
}
return provinces;
}
private void bfs(int[][] isConnected, boolean[] visited, int city) {
Queue<Integer> queue = new LinkedList<>();
queue.add(city); // Start BFS with the given city
visited[city] = true; // Mark the city as visited
while (!queue.isEmpty()) {
int current = queue.poll();
// Explore all connected cities
for (int neighbor = 0; neighbor < isConnected.length; neighbor++) {
if (isConnected[current][neighbor] == 1 && !visited[neighbor]) {
queue.add(neighbor); // Add unvisited neighbors to the queue
visited[neighbor] = true; // Mark neighbor as visited
}
}
}
}
}Solving the Number of Provinces Problem with Disjoint Set (Union-Find)
Why Use Union-Find?
Union-Find is an efficient data structure for determining and managing connected components in a graph. It provides:
1. Efficient Connected Component Detection: Using union and find operations, you can group nodes into components efficiently.
2. Cycle Detection: In undirected graphs, Union-Find can detect cycles.
3. Space Efficiency: Union-Find uses minimal memory compared to BFS or DFS for large graphs.
Steps
1. Initialize Union-Find:
• Create a parent array where each city is its own parent initially.
• Optionally, maintain a rank array for union by rank optimization.
2. Process the Connections:
• Traverse the adjacency matrix isConnected.
• For each connection isConnected[i][j] = 1, perform a union operation to group the cities.
3. Count Provinces:
• After processing all connections, count the number of unique roots in the parent array. Each unique root represents one province.
public class NumberOfProvinces {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length; // Number of cities
UnionFind uf = new UnionFind(n);
// Process connections in the adjacency matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.union(i, j); // Union the two cities
}
}
}
// Return the number of unique provinces (connected components)
return uf.getNumberOfProvinces();
}
// Union-Find class
class UnionFind {
private int[] parent;
private int[] rank;
private int count; // Number of connected components
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n; // Initially, each node is its own component
for (int i = 0; i < n; i++) {
parent[i] = i; // Each city is its own parent initially
}
}
// Find operation with path compression
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
// Union operation with union by rank
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--; // Reduce the number of components
}
}
// Get the number of unique provinces (connected components)
public int getNumberOfProvinces() {
return count;
}
}
}Conclusion
The Number of Provinces problem is a fundamental graph traversal challenge that reinforces core algorithmic concepts like connected components, DFS, BFS, and Union-Find. By mastering these techniques, you gain valuable tools for tackling a wide range of graph-based problems, from social networks to real-world logistics. Each approach—whether it’s the simplicity of DFS, the level-wise exploration of BFS, or the efficiency of Union-Find—offers unique advantages, making them indispensable for different scenarios.
