195. Number of Provinces

🔗 LeetCode Problem: 547. Number of Provinces
📊 Difficulty: Medium
🏷️ Topics: Graph, DFS, BFS, Union-Find, Connected Components

Problem Statement

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the iᵗʰ city and the jᵗʰ city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],
                      [1,1,0],
                      [0,0,1]]

Output: 2

Explanation:
  Cities 0 and 1 are connected: 0 ↔ 1
  City 2 is alone: 2

  Province 1: {0, 1}
  Province 2: {2}

  Total: 2 provinces

Example 2:

Input: isConnected = [[1,0,0],
                      [0,1,0],
                      [0,0,1]]

Output: 3

Explanation:
  No cities are connected.

  Province 1: {0}
  Province 2: {1}
  Province 3: {2}

  Total: 3 provinces (all isolated)

Constraints: - 1 <= n <= 200 - n == isConnected.length - n == isConnected[i].length - isConnected[i][j] is 1 or 0. - isConnected[i][i] == 1 - isConnected[i][j] == isConnected[j][i]

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Given connections between cities, find number of groups: 🏙️

Example:
  Cities: 0, 1, 2, 3
  Connections: 0↔1, 2↔3

  Groups (Provinces):
    Group 1: {0, 1}  (connected to each other)
    Group 2: {2, 3}  (connected to each other)

  Answer: 2 provinces

Key question: How many separate groups of connected cities? 🎯

Understanding the Matrix 📊

isConnected matrix: shows direct connections

Example:
     0  1  2
  0 [1, 1, 0]    City 0: connected to 0 (itself), 1
  1 [1, 1, 0]    City 1: connected to 0, 1 (itself)
  2 [0, 0, 1]    City 2: connected to 2 (itself only)

Visual:
  0 ↔ 1    2

Two provinces! ✅

Another example:
     0  1  2  3
  0 [1, 1, 0, 0]
  1 [1, 1, 1, 0]
  2 [0, 1, 1, 0]
  3 [0, 0, 0, 1]

Connections:
  0↔1, 1↔2  (0,1,2 form one group)
  3 alone   (3 is isolated)

Visual:
  0 ↔ 1 ↔ 2    3

Two provinces: {0,1,2} and {3} ✅

🧠 The Journey - From Real World to Union-Find

Part 1: The Real World Problem - "Friend Groups" 👥

💭 Imagine a classroom with students:

Students: Alice, Bob, Carol, Dave, Eve

Friendships:
  Alice ↔ Bob
  Carol ↔ Dave
  Eve is alone

Question: How many friend groups?

Groups:
  Group 1: {Alice, Bob}
  Group 2: {Carol, Dave}
  Group 3: {Eve}

Answer: 3 friend groups! ✅

This is EXACTLY our provinces problem! 🎯
Just replace "students" with "cities"
and "friendships" with "connections"!

Part 2: The Naive Way - "Ask Everyone!" 🤔

💭 How would you count friend groups in real life?

Approach 1: Start with someone, ask who their friends are

Start with Alice:
  "Who are your friends?"
  Alice: "Bob!"

  "Bob, who are your friends?"
  Bob: "Alice!"

  Group 1 complete: {Alice, Bob} ✅

Start with Carol (unvisited):
  "Who are your friends?"
  Carol: "Dave!"

  "Dave, who are your friends?"
  Dave: "Carol!"

  Group 2 complete: {Carol, Dave} ✅

Start with Eve (unvisited):
  "Who are your friends?"
  Eve: "Nobody!"

  Group 3 complete: {Eve} ✅

Total: 3 groups!

This is DFS/BFS approach! 🌊

Part 3: The Smart Way - "Union-Find Intro" 💡

💭 But there's a SMARTER way using Union-Find!

Real world analogy: School clubs! 🏫

Initially, everyone is their own club:
  Alice's club: {Alice}
  Bob's club: {Bob}
  Carol's club: {Carol}
  Dave's club: {Dave}
  Eve's club: {Eve}

  Total clubs: 5 ✅

Now, process friendships:

Friendship: Alice ↔ Bob
  Action: MERGE their clubs!
  Result:
    AliceBob's club: {Alice, Bob}
    Carol's club: {Carol}
    Dave's club: {Dave}
    Eve's club: {Eve}

  Total clubs: 4 ✅

Friendship: Carol ↔ Dave
  Action: MERGE their clubs!
  Result:
    AliceBob's club: {Alice, Bob}
    CarolDave's club: {Carol, Dave}
    Eve's club: {Eve}

  Total clubs: 3 ✅

No more friendships!
Final answer: 3 groups! 🎯

This is Union-Find! 🌟

Part 4: Union-Find Core Concepts 🔑

✨ Union-Find has THREE key operations:

1️⃣ MAKE-SET: Create individual sets
   Initially, everyone is their own set

2️⃣ FIND: Find which set someone belongs to
   "Who is the leader of your group?"

3️⃣ UNION: Merge two sets together
   "Join these two groups into one!"

Data structure: Array of parents! 📊

Example with 5 people (indices 0-4):
  parent = [0, 1, 2, 3, 4]

  Meaning: Each person is their own parent (own leader)

  Person 0: parent[0] = 0 (leader of self)
  Person 1: parent[1] = 1 (leader of self)
  Person 2: parent[2] = 2 (leader of self)
  Person 3: parent[3] = 3 (leader of self)
  Person 4: parent[4] = 4 (leader of self)

After union(0, 1):
  parent = [0, 0, 2, 3, 4]
         //  ↑
  Person 1 now points to 0 as leader!

  Group: {0, 1} with leader 0

After union(2, 3):
  parent = [0, 0, 2, 2, 4]
              //    ↑
  Person 3 now points to 2 as leader!

  Groups: {0, 1} with leader 0
          {2, 3} with leader 2
          {4}    with leader 4

  Total groups: 3 ✅

Count groups: Count how many are their own parent!
  parent[0] == 0? YES ✅ (leader)
  parent[1] == 1? NO  ❌
  parent[2] == 2? YES ✅ (leader)
  parent[3] == 3? NO  ❌
  parent[4] == 4? YES ✅ (leader)

  Leaders: 3 → Answer: 3 groups! 🎯

Part 5: Union-Find Operations in Detail 🔍

💭 Let's understand FIND and UNION deeply:

╔═══════════════════════════════════════════════╗
║         FIND: "Who's your leader?"            ║
╚═══════════════════════════════════════════════╝

find(x):
  Keep following parent pointers until you find the leader!
  Leader = someone who is their own parent

Example:
  parent = [0, 0, 1, 2]

  find(0):
    parent[0] = 0
    0 == 0? YES! Leader found! ✅
    Return: 0

  find(1):
    parent[1] = 0
    1 == 0? NO
    Follow: go to 0
    parent[0] = 0
    0 == 0? YES! Leader found! ✅
    Return: 0

  find(2):
    parent[2] = 1
    2 == 1? NO
    Follow: go to 1
    parent[1] = 0
    1 == 0? NO
    Follow: go to 0
    parent[0] = 0
    0 == 0? YES! Leader found! ✅
    Return: 0

  find(3):
    parent[3] = 2
    Follow chain: 3 → 2 → 1 → 0 ✅
    Return: 0

All point to same leader 0!
They're in the same group! 🎯

╔═══════════════════════════════════════════════╗
║        UNION: "Merge two groups!"             ║
╚═══════════════════════════════════════════════╝

union(x, y):
  1. Find leader of x's group
  2. Find leader of y's group
  3. Make one leader point to the other!

Example:
  parent = [0, 1, 2]  (3 separate groups)

  union(0, 1):
    leader_0 = find(0) = 0
    leader_1 = find(1) = 1
    Make 1 point to 0:
    parent[1] = 0

    Result: parent = [0, 0, 2]
    Groups: {0, 1} and {2}

  union(1, 2):
    leader_1 = find(1) = 0  (1's leader is 0!)
    leader_2 = find(2) = 2
    Make 2 point to 0:
    parent[2] = 0

    Result: parent = [0, 0, 0]
    Groups: {0, 1, 2} - ALL CONNECTED! ✅

Beautiful! 🌟

Part 6: Why Union-Find is Powerful 💪

💭 Comparing approaches:

DFS/BFS Approach:
  ✅ Easy to understand
  ✅ Works perfectly
  ❌ Builds graph first
  ❌ Visits every node/edge
  Time: O(n²) for this problem

Union-Find Approach:
  ✅ Direct: process connections as we see them
  ✅ No graph needed!
  ✅ Efficient with optimizations
  ✅ Answers "are these connected?" in O(1) amortized!
  Time: O(n²) but with TINY constant factor

Real power shows in DYNAMIC scenarios:
  "Are cities X and Y connected?"
  Union-Find: O(1) amortized! ⚡
  DFS/BFS: O(n) every time! ❌

For this problem, both work!
But Union-Find teaches fundamental pattern! 🎯

🎯 Approach 1: DFS (Easiest to Understand!)

The Key Insight 💡

Use DFS to find connected components 🌊. Treat matrix as graph: if isConnected[i][j] = 1, there's edge i↔j 🔗. For each unvisited city, start DFS to mark all cities in same province 📝. Count how many DFS starts = number of provinces! 🎯. Time: O(n²) ⚡, Space: O(n) 📦!

Classic connected components! ✨

Complete Implementation

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // ═══════════════════════════════════════════════════
        // DFS APPROACH - FIND CONNECTED COMPONENTS 🌊
        // ═══════════════════════════════════════════════════
        // Each DFS explores one complete province
        // Count number of DFS starts = number of provinces!
        // ═══════════════════════════════════════════════════

        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        // ═══════════════════════════════════════════════════
        // TRY STARTING DFS FROM EACH CITY 🚀
        // ═══════════════════════════════════════════════════
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // ───────────────────────────────────────────
                // FOUND NEW PROVINCE! 🎉
                // ───────────────────────────────────────────
                dfs(i, isConnected, visited);
                provinces++;
            }
        }

        return provinces;
    }

    // ═══════════════════════════════════════════════════════
    // DFS: MARK ALL CITIES IN SAME PROVINCE 🔍
    // ═══════════════════════════════════════════════════════
    private void dfs(int city, int[][] isConnected, boolean[] visited) {
        visited[city] = true;

        // ───────────────────────────────────────────────────
        // VISIT ALL CONNECTED CITIES 🌊
        // ───────────────────────────────────────────────────
        for (int other = 0; other < isConnected.length; other++) {
            if (isConnected[city][other] == 1 && !visited[other]) {
                dfs(other, isConnected, visited);
            }
        }
    }
}

Why This Works 🎯

DFS explores entire province: 🌊 - Start from unvisited city - Visit all connected cities recursively - Marks entire province as visited!

Count DFS starts: 📊 - Each DFS start = found new province - Already visited cities don't start new DFS - Total starts = total provinces!

Simple and intuitive: ✨ - Just connected components counting - Standard graph algorithm!

🎯 Approach 2: BFS (Also Easy!)

The Key Insight 💡

Use BFS for level-by-level exploration 🌊. Same idea as DFS but with queue! 🔄 For each unvisited city, BFS marks all connected cities in same province 📝. Time: O(n²) ⚡, Space: O(n) 📦!

BFS alternative! 🌟

Complete Implementation

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // ═══════════════════════════════════════════════════
        // BFS APPROACH - FIND CONNECTED COMPONENTS 🌊
        // ═══════════════════════════════════════════════════

        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // ───────────────────────────────────────────
                // FOUND NEW PROVINCE! BFS to mark all 🎉
                // ───────────────────────────────────────────
                bfs(i, isConnected, visited);
                provinces++;
            }
        }

        return provinces;
    }

    // ═══════════════════════════════════════════════════════
    // BFS: EXPLORE PROVINCE LEVEL BY LEVEL 🔍
    // ═══════════════════════════════════════════════════════
    private void bfs(int start, int[][] isConnected, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int city = queue.poll();

            // ───────────────────────────────────────────────
            // CHECK ALL POTENTIAL CONNECTIONS 🔗
            // ───────────────────────────────────────────────
            for (int other = 0; other < isConnected.length; other++) {
                if (isConnected[city][other] == 1 && !visited[other]) {
                    queue.offer(other);
                    visited[other] = true;
                }
            }
        }
    }
}

🎯 Approach 3: Union-Find (The New Pattern!)

The Key Insight 💡

Use Union-Find data structure for dynamic connectivity! 🔗 Initialize each city as its own set 🏗️. For each connection, union the two cities 🤝. Count final number of disjoint sets = provinces! 📊 Time: O(n² × α(n)) where α is inverse Ackermann (≈ O(1)) ⚡, Space: O(n) 📦!

Efficient and elegant! 🌟

Complete Implementation

class Solution {
    // ═══════════════════════════════════════════════════════
    // UNION-FIND DATA STRUCTURE 🔗
    // ═══════════════════════════════════════════════════════
    private int[] parent;
    private int[] rank;  // For union by rank optimization

    public int findCircleNum(int[][] isConnected) {
        // ═══════════════════════════════════════════════════
        // UNION-FIND APPROACH 🌟
        // ═══════════════════════════════════════════════════
        // Process connections, union cities
        // Count disjoint sets at the end!
        // ═══════════════════════════════════════════════════

        int n = isConnected.length;
        parent = new int[n];
        rank = new int[n];

        // ═══════════════════════════════════════════════════
        // INITIALIZE: Each city is its own set 🏗️
        // ═══════════════════════════════════════════════════
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // Each is its own parent (leader)
            rank[i] = 0;    // Initial rank is 0
        }

        // ═══════════════════════════════════════════════════
        // PROCESS ALL CONNECTIONS 🔗
        // ═══════════════════════════════════════════════════
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // j > i to avoid duplicates
                if (isConnected[i][j] == 1) {
                    union(i, j);  // Merge their sets!
                }
            }
        }

        // ═══════════════════════════════════════════════════
        // COUNT DISJOINT SETS 📊
        // ═══════════════════════════════════════════════════
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == i) {  // Is this a leader?
                provinces++;
            }
        }

        return provinces;
    }

    // ═══════════════════════════════════════════════════════
    // FIND: Get the leader (root) of the set 🔍
    // ═══════════════════════════════════════════════════════
    // With PATH COMPRESSION optimization! ⚡
    // ═══════════════════════════════════════════════════════
    private int find(int x) {
        if (parent[x] != x) {
            // ───────────────────────────────────────────────
            // PATH COMPRESSION: Make x point directly to root
            // ───────────────────────────────────────────────
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // ═══════════════════════════════════════════════════════
    // UNION: Merge two sets 🤝
    // ═══════════════════════════════════════════════════════
    // With UNION BY RANK optimization! ⚡
    // ═══════════════════════════════════════════════════════
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;  // Already in same set!
        }

        // ───────────────────────────────────────────────────
        // UNION BY RANK: Attach smaller tree under larger
        // ───────────────────────────────────────────────────
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

Why This Works 🎯

Union-Find maintains disjoint sets: 🔗 - Each city starts in its own set - Union merges sets when cities connected - Find tells us which set a city belongs to!

Path compression optimization: ⚡ - Makes trees flat - Future finds become O(1)! - parent[x] = find(parent[x])

Union by rank optimization: 📊 - Keeps trees balanced - Attach smaller tree to larger - Prevents long chains!

Count leaders = count sets: 🎯 - Leaders: nodes where parent[i] == i - Each leader represents one province!

🔍 Detailed Dry Run - Union-Find Approach

Let's trace Union-Find on:

isConnected = [[1,1,0],
               [1,1,0],
               [0,0,1]]

╔══════════════════════════════════════════════════════════════╗
║                       INITIALIZATION                         ║
╚══════════════════════════════════════════════════════════════╝

n = 3 cities (0, 1, 2)

Initialize parent and rank:
  parent = [0, 1, 2]  // Each city is its own parent
  rank   = [0, 0, 0]  // All ranks start at 0

Visualization:
  0    1    2    (3 separate sets)

Sets: {0}, {1}, {2}
Count: 3 provinces initially

╔══════════════════════════════════════════════════════════════╗
║                   PROCESS CONNECTIONS                        ║
╚══════════════════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ CHECK: isConnected[0][1] = 1                   ║
╠═════════════════════════════════════════════════╣
║ Connection found: 0 ↔ 1                        ║
║ Call: union(0, 1)                               ║
║                                                 ║
║ Step 1: Find leaders                            ║
║   rootX = find(0) = 0                          ║
║   rootY = find(1) = 1                          ║
║                                                 ║
║ Step 2: Compare ranks                           ║
║   rank[0] = 0                                   ║
║   rank[1] = 0                                   ║
║   Equal ranks! Attach 1 to 0                    ║
║                                                 ║
║ Step 3: Union                                   ║
║   parent[1] = 0                                ║
║   rank[0]++  (0 → 1)                           ║
║                                                 ║
║ Result:                                         ║
║   parent = [0, 0, 2]                           ║
║   rank   = [1, 0, 0]                           ║
║                                                 ║
║ Visualization:                                  ║
║     0                                           ║
║     ↑                                           ║
║     1        2                                  ║
║                                                 ║
║ Sets: {0, 1}, {2}                              ║
║ Count: 2 provinces now!                         ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ CHECK: isConnected[0][2] = 0                   ║
╠═════════════════════════════════════════════════╣
║ No connection! Skip!                            ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ CHECK: isConnected[1][2] = 0                   ║
╠═════════════════════════════════════════════════╣
║ No connection! Skip!                            ║
╚═════════════════════════════════════════════════╝

╔══════════════════════════════════════════════════════════════╗
║                    COUNT PROVINCES                           ║
╚══════════════════════════════════════════════════════════════╝

Final state:
  parent = [0, 0, 2]

Count leaders (parent[i] == i):
  parent[0] == 0? YES ✅ Leader found! Count = 1
  parent[1] == 1? NO  ❌ (parent[1] = 0)
  parent[2] == 2? YES ✅ Leader found! Count = 2

Total provinces: 2 ✅

╔══════════════════════════════════════════════════════════════╗
║                    FINAL RESULT: 2                           ║
╠══════════════════════════════════════════════════════════════╣
║                                                              ║
║  Province 1: Cities {0, 1}  (leader: 0)                    ║
║  Province 2: City {2}        (leader: 2)                    ║
║                                                              ║
║  Visual:                                                     ║
║    0 ↔ 1      2                                             ║
║                                                              ║
║  Answer: 2 provinces! 🎯                                    ║
║                                                              ║
╚══════════════════════════════════════════════════════════════╝

🔑 Key Observations:

Union merges sets: 🤝 Cities 0 and 1 merged into one set
Path compression not needed here: ⚡ Trees are already flat (depth 1)
Union by rank keeps balanced: 📊 Prevented unnecessary depth
Counting leaders gives answer: 🎯 2 leaders = 2 provinces
Efficient processing: ✨ Each connection processed in O(α(n)) ≈ O(1)

📊 Complexity Analysis

DFS/BFS Approaches

Time Complexity: O(n²) ⚡

Where n = number of cities

For each city: O(n)
  DFS/BFS visits: O(n) in worst case
  Check all connections: O(n)

Total: O(n) cities × O(n) = O(n²)

Example: n = 200
  Operations: 40,000 ✅ Very fast!

Space Complexity: O(n) 📦

Recursion stack (DFS): O(n) worst case
Queue (BFS): O(n) worst case
Visited array: O(n)

Total: O(n) 📦

Union-Find Approach

Time Complexity: O(n² × α(n)) ⚡

Where α(n) is inverse Ackermann function

Initialize: O(n)
Process connections: O(n²) pairs
  Each union/find: O(α(n)) ≈ O(1) amortized!

Total: O(n²) practically!

α(n) is INCREDIBLY small:
  n = 10^80 (atoms in universe): α(n) ≤ 4!
  For all practical n: α(n) ≤ 5

So effectively O(n²)! ⚡

Space Complexity: O(n) 📦

Parent array: O(n)
Rank array: O(n)

Total: O(n) 📦

🔗 Union-Find Pattern Deep Dive

When to Use Union-Find 🎯

✅ Perfect for Union-Find:
  • "Count connected components"
  • "Are X and Y connected?"
  • "Merge two groups"
  • "Dynamic connectivity"
  • "Disjoint sets"

🔍 Recognition keywords:
  • "Connected"
  • "Group"
  • "Component"
  • "Cluster"
  • "Merge"
  • "Union"

📊 Problem types:
  • Network connectivity
  • Friend circles
  • Island counting (alternative)
  • Redundant connections
  • Graph connectivity

Union-Find Template 📋

class UnionFind {
    private int[] parent;
    private int[] rank;

    // Constructor: Initialize
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // Each is own parent
        }
    }

    // Find with path compression
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression!
        }
        return parent[x];
    }

    // Union with rank
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false;  // Already connected
        }

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true;  // Successfully united
    }

    // Check if connected
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    // Count components
    public int countComponents() {
        int count = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == i) count++;
        }
        return count;
    }
}

Optimizations Explained 🔍

Path Compression: ⚡

Without path compression:
  Chain: 0 → 1 → 2 → 3 → 4
  find(4): 4 hops to reach 0!

With path compression:
  After find(4):
  All point directly to 0!

     0
   / | \ \
  1  2  3  4

  Next find(4): 1 hop! ⚡

Implementation:
  parent[x] = find(parent[x])

This makes trees flat!
Future operations: O(1)! 🚀

Union by Rank: 📊

Without union by rank:
  Might create long chains:
  0 → 1 → 2 → 3 ... → n
  Bad! O(n) finds!

With union by rank:
  Always attach smaller tree to larger:
  Keeps trees balanced!

Example:
  Tree A (rank 2):      Tree B (rank 1):
      0                     5
     / \                    |
    1   2                   6
    |
    3

  Union A and B:
  Attach B under A (A has higher rank):
      0
     / | \
    1  2  5
    |     |
    3     6

  Still balanced! Depth increases slowly!

Guarantees: O(log n) depth worst case
With path compression: O(α(n)) amortized! 🌟

📝 Quick Revision Notes

🎯 Core Concept

Number of Provinces finds connected components in undirected graph 📊. Three approaches: DFS (start from each unvisited, explore component) 🌊, BFS (queue-based exploration) 🔄, Union-Find (merge connected cities, count disjoint sets) 🔗. Union-Find uses parent array to track set leaders 👥. Path compression makes trees flat ⚡. Union by rank keeps balanced 📊. Count nodes where parent[i] == i = answer! 🎯 Time: O(n²) ⚡, Space: O(n) 📦!

⚡ Quick Implementation (Union-Find)

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
  public int findCircleNum(int[][] isConnected) {
    // // Approach 1 - DFS
    // return dfs(isConnected);

    // Approach 2 - BFS
    return bfs(isConnected);
  }

  private int bfs(int[][] cities) {
    int count = 0;
    HashSet<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    for (int city1 = 0; city1 < cities.length; city1++) {
      if (!visited.contains(city1)) {
        visited.add(city1);
        queue.offer(city1);

        while (!queue.isEmpty()) {
          int curr = queue.poll();

          for (int city2 = 0; city2 < cities.length; city2++) {
            if (!visited.contains(city2) && cities[curr][city2] == 1) {
              visited.add(city2);
              queue.offer(city2);
            }
          }
        }

        count++;
      }
    }

    return count;
  }

  private int dfs(int[][] cities) {
    int count = 0;
    HashSet<Integer> visited = new HashSet<>();

    for (int city1 = 0; city1 < cities.length; city1++) {
      if (!visited.contains(city1)) {
        visited.add(city1);
        dfsUtil(city1, cities, visited);

        count++;
      }
    }

    return count;
  }

  private void dfsUtil(int city1, int[][] cities, HashSet<Integer> visited) {
    for (int city2 = 0; city2 < cities.length; city2++) {
      if (!visited.contains(city2) && cities[city1][city2] == 1) {
        visited.add(city2);
        dfsUtil(city2, cities, visited);
      }
    }
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.findCircleNum(new int[][] { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } })); // 2
    System.out.println(s.findCircleNum(new int[][] { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } })); // 3
  }
}

🔑 Key Insights

Union-Find Three Operations: 🔗

The foundation of Union-Find:

1️⃣ MAKE-SET: parent[i] = i
   Create individual sets

2️⃣ FIND: Follow parent pointers to root
   find(x):
     if (parent[x] != x)
       parent[x] = find(parent[x])  // Path compression!
     return parent[x]

3️⃣ UNION: Merge two sets
   union(x, y):
     rootX = find(x)
     rootY = find(y)
     parent[rootX] = rootY  // Simple version

These three operations solve ALL connectivity problems! 🎯

Path Compression Magic: ⚡

Why it's brilliant:

Without compression:
  Long chain: 0 → 1 → 2 → 3 → 4 → 5
  find(5): 5 hops! ❌

With compression:
  First find(5): 5 hops
  But flattens tree:
       0
      /|\\\
     1 2 3 4 5

  Next find(5): 1 hop! ✅
  Next find(4): 1 hop! ✅
  Next find(3): 1 hop! ✅

All future finds: O(1)! ⚡

Implementation: Just one line!
  parent[x] = find(parent[x])

This recursively flattens entire path!
Genius! 🌟

Union by Rank Strategy: 📊

Why rank matters:

Bad union (always attach right to left):
  Union(0,1): 0 → 1
  Union(1,2): 0 → 1 → 2
  Union(2,3): 0 → 1 → 2 → 3

  Result: Long chain! ❌

Good union (by rank):
  Track tree "height" (rank)
  Always attach shorter tree to taller!

  Union trees of rank 1 and 2:
    Attach rank-1 under rank-2
    Final rank: still 2! ✅

  Union trees of equal rank:
    Attach either way
    Final rank: increase by 1

  Keeps trees balanced! 📊
  Guarantees: depth ≤ log n

With path compression + rank:
  Amortized: O(α(n)) ≈ O(1)! ⚡

Nearly constant time! Magic! ✨

Counting Components: 🎯

The beautiful trick:

After all unions, count leaders!

Leader = node where parent[i] == i

Example:
  parent = [0, 0, 2, 0, 4]

  Check each:
    parent[0] == 0? YES ✅ Leader 1
    parent[1] == 1? NO  ❌
    parent[2] == 2? YES ✅ Leader 2
    parent[3] == 3? NO  ❌
    parent[4] == 4? YES ✅ Leader 3

  Count = 3 components! 🎯

Why this works:
  Each leader represents one disjoint set
  Non-leaders point to their leader

Simple and elegant! 🌟

🎪 Memory Aid

"Union-Find keeps sets apart" 🔗
"Path compression makes it smart" ⚡
"Union by rank keeps trees flat" 📊
"Count leaders, and that's that!" 🎯 ✨

⚠️ Don't Forget

Initialize parent[i] = i - everyone starts separate! 🏗️
Path compression in find - flatten while finding! ⚡
Union by rank - attach smaller to larger! 📊
Check rootX != rootY - before union! 🔍
Count where parent[i] == i - these are leaders! 👑
Three approaches all work - choose based on context! 🎯

🎉 Congratulations!

You've learned Union-Find - a fundamental algorithm pattern! 🌟

What You Learned:

✅ Union-Find data structure - parent array tracking! 🔗
✅ Path compression - O(1) amortized finds! ⚡
✅ Union by rank - balanced trees! 📊
✅ Connected components - in any graph! 🎯
✅ Dynamic connectivity - real-time queries! 🚀

The Beautiful Pattern:

Union-Find solves connectivity in 3 operations:
  1. MAKE-SET: Initialize
  2. FIND: Get leader
  3. UNION: Merge sets

With optimizations:
  - Path compression: O(α(n)) finds
  - Union by rank: balanced trees

Result: Nearly O(1) operations! ⚡

This will be your foundation for:
  ✅ Redundant connections
  ✅ Accounts merge
  ✅ Number of islands (alternative)
  ✅ Graph connectivity
  ✅ Minimum spanning tree

Master this pattern = unlock graph algorithms! 🔑

Next problems will build on this foundation! 🚀
Union-Find is your new superpower! 💪✨🎯