Задача(Описание внутри)

[airesjke]

Изолированные города

В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве.

Формат входного файла

Во входном файле записаны сначала два числа N и M, задающие соответственно количество городов и количество дорог (1≤N≤100, 0≤M≤1000), а затем перечисляются попарно связанные дорогами города. Каждая дорога задается номерами городов, которые она соединяет.
Формат выходного файла

В выходной файл выведите одно число – количество штатов в государстве.

Примеры:

input.txt 6 3 1 3 1 5 2 6 output.txt 3
input.txt 7 0 output.txt 7

[BDA]

http://programmersforum.ru/showthread.php?t=234680
http://programmersforum.ru/showthread.php?t=234721

Не многовато ли тем с одной и той же задачей?
У Вас за это время какие-нибудь мысли по ее реализации возникли?

Алгоритм, пришедший в голову (скорее всего, не оптимальный):
Считать N и M
Завести массив N на N
Считать M дорог и установить в массиве единички на пересечении тех строки и столбца, чьи номера совпадают со считанными номерами городов
Завести массив длины N
Завести переменную - количество штатов, равную 0
Цикл по всем элементам массива длины N (поиск не посещенных городов)
Записать в первый найденный нулевой элемент массива единицу, увеличить счетчик штатов и запустить обход в глубину для этого города (последовательное посещение всех городов, с которыми есть дорога)
Как только собираемся посетить город, смотрим на его состояние по массиву длины N
Если там 0, значит он не посещен - ставим 1 и вызываем посещение доступных ему городов, иначе выходим из рекурсии
Выводим количество штатов

[s-andriano]

Мне что-то кажется, лучше действовать таким образом:
0. Предпринять действия, позволяющие в дальнейшем оптимальнее искать города, соединенные дорогами с данным:
0.1. Определяем структура из двух чисел, описывающая дорогу.
0.2. Заводим массив этих структур длиной 2М.
0.3. Каждую считанную дорогу записываем в этот массив дважды: в прямом и обратном направлении.
0.4. Сортируем массив по первому полю для обеспечения бинарного поиска.
Таким образом сокращаем как объем необходимой памяти, так и сложность алгоритма.

[BDA]

s-andriano, согласен. Еще можно попробовать взять map<int, vector<int> > (т.к., похоже, решение нужно именно на c++).
P.S. Вся программа - 50 строчек.