Count the Separate Friend Circles

Medium20–25 min

Topics

GraphDFSConnected ComponentsAdjacency Matrix

Companies

AmazonMicrosoftGoogleFacebookUber

There are n people, and some of them are direct friends. The friendships are given as an n × n adjacency matrix: isConnected[i][j] = 1 if person i and person j are direct friends, and 0 otherwise (the matrix is symmetric and every person is a "friend" of themselves on the diagonal). A friend circle is a group of people connected through chains of direct friendships, and it cannot be enlarged with anyone else. Return the number of friend circles.

Equivalently: count the connected components of an undirected graph given as an adjacency matrix.

Test Case 1:

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

Output:3

Explanation:As an adjacency list: 0:[1,4], 1:[0], 2:[3], 3:[2], 4:[0], 5:[]. Person 0 knows 1 and 4, so {0, 1, 4} is one circle; {2, 3} is a second; person 5 alone is the third.

Test Case 2:

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

Output:2

Explanation:Adjacency list 0:[], 1:[]. Nobody knows anybody: every person is a circle by themselves.

Test Case 3:

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

Output:1

Explanation:Everybody is a direct friend of everybody: one circle.

Constraints

◆1 ≤ n ≤ 20 people, numbered 0 … n − 1
◆isConnected is an n × n adjacency matrix: isConnected[i][j] = 1 means person i and person j are direct friends, 0 means they are not. It is symmetric and isConnected[i][i] = 1
◆Friendship is transitive for circle purposes: a circle is a maximal group of people in which everybody is connected to everybody else through a chain of direct friends (a connected component of the friendship graph)
◆Return the number of circles (connected components), counting a person with no friends as a circle of their own

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Keep Lowering Labels Until Nothing Changes

Brute

Give every person a label equal to their own number. Then sweep over all pairs again and again: whenever person i is a friend of person j and j carries a smaller label, person i takes that smaller label. Labels spread through friendships, so when a full sweep changes nothing, everyone in a circle carries the same label — the smallest number in the circle. The circles are then exactly the people whose label equals their own number. A single sweep costs O(n²), and information needs up to n sweeps to travel across a long chain of friends: O(n³) in the worst case.

TimeO(n³)

SpaceO(n)

Java

Try it out

class Solution {
    public int countProvinces(int[][] isConnected) {
        int n = isConnected.length;
        int[] label = new int[n];
        for (int i = 0; i < n; i++) label[i] = i;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (isConnected[i][j] == 1 && label[j] < label[i]) {
                        label[i] = label[j];
                        changed = true;
                    }
                }
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (label[i] == i) count++;
        }
        return count;
    }
}

Optimal — Depth-First Search From Every Unvisited Person

Optimal

Walk through the people in order. Each time you meet somebody who has not been visited yet, they belong to a circle nobody has counted: count one more circle and explore the whole circle from that person — mark the person visited, then for every friend (a 1 in the person's row of the matrix) that is not visited yet, explore them the same way. Everybody reachable through friendships gets marked, so no circle is counted twice. Every row of the matrix is scanned once: O(n²) time, O(n) for the visited marks and the recursion.

TimeO(n²)