Выберите любой узел на графике. Этот узел принадлежит какому-то компоненту, и он может существовать с несколькими другими узлами. Итак, запустите BFS, раскрасьте этот узел и все, что с него можно сделать, золотом. Это один компонент.
Теперь выберите другой узел. Одна из двух вещей должна быть правдой об этом. Во-первых, это может быть случай, когда узел уже выкрашен золотом. В этом случае вы уже подсчитали компонент, который его содержит. Во-вторых, это может быть неокрашенным. В этом случае вы не посчитали его компонент, поэтому раскрасьте его и все узлы, доступные из него золотом, и это ваш второй компонент.
Как вы думаете, вы можете обобщить эту идею, чтобы подсчитать все компоненты ?
Что касается времени выполнения - сколько раз каждый узел посещается таким образом? Помните, что вы рисуете каждый узел золотом только один раз, и что каждое ребро посещается только в курсе или узлах рисования.