Интервью: о поиске людей

Я видел это вопрос интервью недавно для фирмы, которая сказала:

Группа людей, вы можете позвонить Знать (i, j) , чтобы спросить, i -й человек знает j th, возвращаемое значение - true ( i знает j ) или false ( i не знает j ). Найдите человека, которого все знают, но он никого не знает.

Я могу придумать реализацию O (N ^ 2) , чтобы вы просто соответствовали каждому человеку с любым другим методом, устраняя всех, кто действительно кого-то знает. Однако я r не может придумать более быстрой реализации, чем эта.

Кто-нибудь может помочь или подсказать?