Время работы DFS при проверке тесно связанных компонентов

Question

Рассмотрим группу из k человек.Я хочу проверить, дружит ли каждый человек в группе со всеми другими людьми в группе.

Чтобы проверить, все ли люди дружат друг с другом, я бы запустил DFS для каждого человека, проверяя, дружат ли они с k-1 людьми.Если это так, то можно сделать вывод, что они все дружат друг с другом.

DFS имеет время работы O (V + E).Продолжительность времени все еще O (V + E), если я делаю DFS для каждого человека?

Answer 1

DFS имеет время работы O (V + E). Время работы все еще O (V + E) если я сделаю DFS для каждого человека?

Нет, так как вы выполняете поиск V раз, у вас будет O(V * (V+E))

Вероятно, хотя вы этого и не хотите, вы можете сделать это в O(V), используя свойства полного графа, т. Е.) Граф завершен, если каждый узел имеет степень V-1. Обратите внимание, что график также должен быть простым, но он должен быть в вашем случае