Skip to main content

Friend Group Counter

easy
Union FindGraphUnion Find Components
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Description

You are given `n` people numbered `0` to `n-1` and a list of friendship pairs. Two people are in the same friend group if they are directly or indirectly connected through friendships.

Return the **total number of distinct friend groups**.

**Example 1:**
```
Input: n = 6, connections = [[0,1],[1,2],[3,4]]
Output: 3
Explanation: Groups are {0,1,2}, {3,4}, {5}. Person 5 is alone.
```

**Example 2:**
```
Input: n = 4, connections = [[0,3],[1,2],[0,2]]
Output: 2
Explanation: Groups are {0,1,2,3} and nothing else — all merge.
```

Constraints

  • 1 <= n <= 10^4
  • 0 <= connections.length <= 10^4
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • No duplicate connections

Follow-up

Can you also return the size of the largest friend group?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.