Подсчет числа компонент связности С++

[Li*zA]

Здравствуйте.
Очень нужна ваша помощь, сама уже устала этим заниматься. Неполучается.

Мне нужно найти число компонент связности, т.е. колличество несвязных (под)графов в одном большом графе, который задан матрицей смежности.
Делается это, вроде, поиском в глубину, но как это реализовать, я не знаю.

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

Вот мой код, но он не особо поможет с подсчетом числа компонент связности

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

int main ()
{
setlocale(LC_ALL,"rus");
int vert;					// Колличество вершин
int rib = 0;				// Удвоенное колличество ребер + колличество петель (т.е. единиц в матрице)
int loop = 0;				// Колличество петель 
ifstream fin("1.txt");
fin>>vert;					
if (vert < 1)
{
	cout << "ERROR(это не граф) ";
	return 1;
}
int **graph = new int*[vert];
	for(int i=0;i<vert; i++)
		{
			graph[i] = new int[vert];
		}	
		//Ввод таблицы из файла
		for (int i = 0; i < vert; i++ )
		{    
			for (int j = 0; j < vert; j++ )
			{	 
				fin >> graph[i][j]; 
				if (graph[i][j] == 1)
				{
					rib++;
				}
				else if (graph[i][j] == 0){}
				else 
				{
					cout << "ERROR(некорректные входные данные) ";
					return 1;
				}
			}
			if (graph[i][i] == 1)
				{
					loop=loop+1;
				}
		}
		cout << "Матирца смежности заданного графа:\n" ;
							//Вывод таблицы
		for (int i = 0; i < vert; i++ )
		{ 
			for (int j = 0; j < vert; j++ )
			{ 
				cout<<setw(5)<< graph[i][j] ; 
			}
				cout<<"\n" ; 
		}
		int result;
		result = 1 + (rib+loop)/2 - vert; // вместо еденички надо число компонент связности
		cout << "Цикломатическое число заданного графа = " ;
		cout << result << "\n";
}

Если кто поможет, буду очень признательна

PS Если создала тему не там, прошу простить.

[Son Of Pain]

Там же нет ничего сложного )

Берешь первую вершину, запускаешь с нее обход (поиск) в глубину (или в ширину, тут без разницы), отмечая все пройденные вершины. Когда поиск остановится - отмечены будут все вершины из первой компоненты связности. Дальше повторяешь поиск, начиная его с первой еще непомеченной вершины. И так пока все вершины не станут помеченными.

Естественно, это работает только для неориентированного графа )

[Li*zA]

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

[Son Of Pain]

Реализовывать проще всего рекурсивно )
Добавляешь массив bool visited[vert], в котором будут храниться признаки посещенности вершин, и в цикле

пока (остались непосещенные вершины)
   вызвать обход в глубину или ширину, начиная с первой непосещенной вршины;
   увеличить счетчик компонент связности;

Что конкретно не получается? )