Count Friend Circles
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.
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:
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:
0 to N-1.[u, v] is given, it means u is friends with v and v is friends with u.friendships might contain duplicate pairs, or pairs [u,u], but your solution should handle them gracefully (e.g., by ignoring duplicates or self-friendships).N is 0, there are 0 friend circles. If friendships is empty, each user forms their own circle, resulting in N circles.Examples
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}.
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}.
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
0 <= N <= 10000 <= friendships.length <= N * (N - 1) / 2[u, v]:
0 <= u, v < Nu != v (users cannot be friends with themselves in this context, although your code should not break if such a pair is present)find (with path compression) and union operations (preferably with union by rank or size).friendships list or a small N value (e.g., N=0, N=1).Loading editor...