Frontend School

Count Friend Circles

DSA
easy

Count Friend Circles

Easy
Union Find
Graph
Disjoint Set

Overview

In a social networking platform, users can form friend circles. A friend circle is a group of users who are directly or indirectly friends. If User A is friends with User B, and User B is friends with User C, then A, B, and C all belong to the same friend circle. Understanding the number of distinct friend circles helps in analyzing community structures and user engagement patterns within the platform.

What you need to do / Task

Your task is to implement a function countFriendCircles that takes the total number of users N and a list of direct friendships as input. You need to determine and return the total number of distinct friend circles present in the network.

Input & output

Input:

  • N: An integer representing the total number of users, indexed from 0 to N-1.
  • friendships: A 2D array (list of pairs), where each inner array [u, v] indicates that user u and user v are directly friends.

Output:

  • A single integer representing the total number of distinct friend circles.

Clarifications

  • Users are 0-indexed, from 0 to N-1.
  • Friendships are bi-directional; if [u, v] is given, it means u is friends with v and v is friends with u.
  • The input friendships might contain duplicate pairs, or pairs [u,u], but your solution should handle them gracefully (e.g., by ignoring duplicates or self-friendships).
  • If N is 0, there are 0 friend circles. If friendships is empty, each user forms their own circle, resulting in N circles.

Examples

1

Example 1

Input:

N = 3, friendships = [[0, 1], [1, 2]]

Output:

1

Note:

Users 0 and 1 are friends. Users 1 and 2 are friends. Therefore, 0, 1, and 2 are all indirectly friends, forming one single friend circle: {0, 1, 2}.

2

Example 2

Input:

N = 3, friendships = [[0, 1]]

Output:

2

Note:

Users 0 and 1 are friends. User 2 is not friends with anyone. This forms two distinct friend circles: {0, 1} and {2}.

3

Example 3

Input:

N = 4, friendships = [[0, 1], [2, 3]]

Output:

2

Note:

Users 0 and 1 are friends. Users 2 and 3 are friends. There are no friendships connecting these two pairs. This forms two distinct friend circles: {0, 1} and {2, 3}.

Constraints

Constraints & assumptions

  • 0 <= N <= 1000
  • 0 <= friendships.length <= N * (N - 1) / 2
  • For each friendship [u, v]:
    • 0 <= u, v < N
    • u != v (users cannot be friends with themselves in this context, although your code should not break if such a pair is present)
  • The graph formed by friendships is undirected.

What interviewers evaluate

  • Correctness and Efficiency: Your Union-Find implementation should correctly identify all connected components with optimal time complexity.
  • Data Structure Usage: Proper initialization and manipulation of the Union-Find data structure (parent array, optionally rank/size array).
  • Algorithm Implementation: Clear and correct implementation of find (with path compression) and union operations (preferably with union by rank or size).
  • Edge Case Handling: Ability to handle cases like an empty friendships list or a small N value (e.g., N=0, N=1).

Loading editor...