Cod sursa(job #2954699)

Utilizator juincPopescu Marian juinc Data 15 decembrie 2022 08:28:02
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>

void DFS(std::vector<std::vector<int>> graph, std::vector<bool>& visited, int node)
{
	visited[node] = true;
	for (int i = 0; i < graph[node].size(); i++)
	{
		if (visited[graph[node][i]] == false)
		{
			DFS(graph, visited, graph[node][i]);
		}
	}
}


int main()
{
	std::ifstream fin("dfs.in");
	std::ofstream fout("dfs.out");
	int n, m;
	fin >> n >> m;

	std::vector<std::vector<int>> graph(n+1);
	std::vector<bool> visited(n+1, false);

	for (int i = 0; i < m; i++)
	{
		int nod1, nod2;
		fin >> nod1 >> nod2;

		graph[nod1].push_back(nod2);
		graph[nod2].push_back(nod1);
	}

	int conex = 0;
	for(int i = 1; i <= n ; i++)
	{
		if (visited[i] != true)
		{
			DFS(graph, visited, i);
			conex++;
		}
	}

	fout << conex;

	fin.close();
	fout.close();
	return 0;
}