Editorial for Binarysearch.io New Friends Solution

Problem statement

You are given n people represented as an integer from 0 to n - 1, and a list of friends tuples, where person friends[i][0] and person friends[i][1] are friends. Return whether everyone has at least one friend.

Problem Link

Intuition

Treat each person as an entry in a set. As we traverse the friends array remove elements from set that have friends. Return true if set is empty.

We initialize nodes as a set of n elements from [0, n)

For each friendship p1, p2 remove both p1 and p2 from the nodes set.

class Solution:
    def solve(self, n, friends):
        nodes = set([i for i in range(n)])
        for p1, p2 in friends:
            if p1 in nodes:
                nodes.remove(p1)
            if p2 in nodes:
                nodes.remove(p2)

        return len(nodes) == 0

Time complexity

O(V+E)

Space complexity

O(V)