Как найти количество компонент связности графа?

Question

[Alone_Fox]

for (int i = 0; i < n; i++)
    {
        if (was[i] != -1)
           continue;
        q.push(i);
        while (!q.empty())
        {
              int v = q.front();
              q.pop();
              if (was[v] != -1)
                 continue;
              was[v] = cur;
              for (int j = 0; j < n; j++)
                  if (mas[i][j] != 0 && was[j] == -1)
                     q.push(j);
        }
        cur++;
    }

Данный код считает максимальную компоненту связности. Как найти их количество?
Например,
3
0 0 0
0 0 1
0 1 0
Эта программа выводит 3, а количество будет равно 2.

Answer 1

[Rsa97]

Выбираете первую вершину графа, отмечаете её и все связанные с ней точки (прямо или чрез другие вершины). Получаете первую компоненту. Выбираете следующую непомеченную вершину графа, от неё получаете вторую компоненту и т.д., пока не останется непомеченных вершин.

Comments

[Alone_Fox]

Как это сделать?

[Rsa97]

Alone_Fox, Пардон, вы хотите, чтобы за вас всё написали? Так это вам на Фрилансим

Answer 2

[xdgadd]

Вот.