Number of Provinces

Given an n x n adjacency matrix isConnected where isConnected[i][j]=1 means cities i and j are directly connected, find the number of provinces (connected components).

Example 1

Input: [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Example 2

Input: [[1,0,0],[0,1,0],[0,0,1]] → Output: 3

Solution Approach

Union-Find: union all pairs (i,j) where isConnected[i][j]==1. Count distinct roots.

Initialize parent[i]=i.
For i from 0 to n-1: for j from i+1 to n-1: if isConnected[i][j]==1: union(i,j).
Count i where find(i)==i.

Java

class Solution {
    int[] parent;
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if (isConnected[i][j] == 1) union(i,j);
        int count = 0;
        for (int i = 0; i < n; i++) if (find(i)==i) count++;
        return count;
    }
    private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
    private void union(int a, int b) { parent[find(a)]=find(b); }
}

Time Complexity: O(N^2 * alpha(N))
Space Complexity: O(N)