Graph Depth First Search Breadth First Search Union Find

There are N students in a class. Some of them are friends, while others are not. Friendship is transitive: - If A is a friend of B - And B is a friend of C - Then A is also a friend of C A friend circle is a group of students who are directly or indirectly friends. You must implement: int friendCircles(char[][] friends) or int friendCircles(List<String> friends)

This function returns the number of friend circles in the class.

The input friends is an N × N matrix of characters 'Y' or 'N':

  • friends[i][j] = 'Y' → student i and student j are friends
  • friends[i][j] = 'N' → they are not friends

Self‑connections such as (0,0), (1,1), (2,2) should not be counted as edges.

Example

Given the matrix:

  0 1 2 3
0 Y Y N N
1 Y Y Y N
2 N Y Y N
3 N N N Y

Interpretation

  • Students are labeled 0, 1, 2, 3
  • Each row/column pair indicates whether two students are connected
  • Example: In row 0, "YYNN" means:
    • 0–0 → ignore (self)
    • 0–1 → connected
    • 0–2 → not connected
    • 0–3 → not connected

Goal

Find the number of connected components in this graph, where 'Y' represents an edge.

Constraints

  • Time Complexity: O(N²)
  • Space Complexity: O(N)

Interpretation of edges

0 ↔ 1

1 ↔ 2

3 is only connected to itself (ignore self‑loops)

Graph:
(0) —– (1) —– (2)

(3)

Explanation

Students 0, 1, and 2 form one connected component (a friend circle).

Student 3 is isolated and forms its own friend circle.

So the graph has 2 friend circles.

Solution:

java


int friendCircles(List<String> friends) {
    int n = friends.size();
    boolean[] visited = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(friends, visited, i);
            count++;
        }
    }

    return count;
}

private void dfs(List<String> friends, boolean[] visited, int student) {
    visited[student] = true;
    String connectedStudents = friends.get(student);
    for (int j = 0; j < connectedStudents.length(); j++) {
        if (connectedStudents.charAt(j) == 'Y' && !visited[j] && student != j) {
                dfs(friends, visited, j);
        }
    }
}

python


def friend_circles(friends):
    n = len(friends)
    visited = [False] * n
    count = 0

    def dfs(student):
        visited[student] = True
        for j in range(n):
            if friends[student][j] == 'Y' and not visited[j] and student != j:
                dfs(j)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1

    return count

friends = [
    "YYNN",
    "YYYN",
    "NYYN",
    "NNNY"
]

print(friend_circles(friends))  # Output: 2

Time Complexity: O(N²)

Space Complexity: O(N)

Github - Finding Friend Circles

Author: Mohammad J Iqbal

Mohammad J Iqbal

Follow Mohammad J Iqbal on LinkedIn