 All Problems
Friend Circles (Number of Provinces) — Weighted Variant
medium
union-find
graph
facebook
google

You are given n people and a list of direct friendship pairs. Find the total number of friend groups. Also return the size of the largest friend group.

Output two integers: number of groups and size of the largest group.

Example 1:

Input: n=5, pairs=[[0,1],[1,2],[3,4]]
Output: 2 3
(Groups: {0,1,2} size 3, {3,4} size 2)

Example 2:

Input: n=4, pairs=[[0,1],[2,3],[1,2]]
Output: 1 4

Constraints:

  • 1 <= n <= 10^5
  • 0 <= pairs.length <= 10^5
Run to check your code against the sample cases, or submit to run every case