Groups Where Everyone Knows Everyone

Medium

A village has people residents numbered from 0 to people - 1. Each pair [a, b] in friendships means a and b know each other (both ways). A *group* is a set of residents linked by chains of acquaintances that nobody outside can join: no one inside knows anyone outside. A loner with no acquaintances is a group too. Return the number of groups in which **every** member directly knows **every** other member.

Example 1

people=5, friendships=[[0, 1], [1, 2], [2, 0], [3, 4]] → 2

Groups {0, 1, 2} and {3, 4}: in each, everyone knows everyone.

Example 2

people=4, friendships=[[0, 1], [1, 2], [3, 0]] → 0

All four are in one group, but 0 and 2, for example, are strangers, so the answer is 0.

Example 3

people=3, friendships=[] → 3

Constraints

1 ≤ people ≤ 50
0 ≤ len(friendships) ≤ people · (people − 1) / 2
0 ≤ a, b ≤ people − 1, a ≠ b
Each pair of acquaintances is listed at most once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Graph

Similar problems

Do the Links Form a Tree Medium Isolated Groups in a Network Medium Ratio Chain Queries Medium Clusters of Linked Servers Medium The Extra Cable Medium

Input

people=5, friendships=[[0, 1], [1, 2], [2, 0], [3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 60 tests on the server, hidden ones included.