Count Friend Groups

Medium
Graph DFS Connected Components
🏢Twitter
0 views0 likes

Problem Description

Count Friend Groups

Given a classroom of N students and their friendships represented as an adjacency list, determine the number of friend groups. A friend group is defined as the smallest set where no student in the group has friends outside the group.

Write a function that takes a dictionary representing the adjacency list and returns the number of friend groups.

Example 1: 

Input: {0: [1, 2], 1: [0, 5], 2: [0], 3: [6], 4: [], 5: [1], 6: [3]}
Output: 3

Example 2: 

Input: {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3], 5: []}
Output: 3

Constraints:

  • The adjacency list represents friendships among N students.
  • Each student is represented by a unique integer from 0 to N-1.

Hints

Use DFS to traverse the friendships.

Track visited students to avoid counting the same group multiple times.

Solution