Cod sursa(job #2676247)

Utilizator claudiaECiontu Claudia claudiaE Data 23 noiembrie 2020 20:26:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<iostream>
#include<fstream>
#include <vector>
using namespace std;
int n, m;
int marked[100005];
std::vector<int> g[100005];
int dfs(int node) {

	//    std::cout << "Marked node " << node << '\n';

	marked[node] = 1;

	for (int i = 0; i < g[node].size(); i++) {

		int new_node = g[node][i];

		if (!marked[new_node])

			dfs(new_node);

	}

}

int main()
{
    ifstream f("DFS.in");
    ofstream fout("DFS.out");
   
	f >> n >> m;

	for (int i = 1; i <= m; i++)

	{

		int a, b;

		f>> a >> b;

		g[a].push_back(b);

		g[b].push_back(a);

	}



	int cont = 0;



	for (int i = 1; i <= n; i++)

	{

		if (!marked[i])

		{

			dfs(i);

			cont++;

		}

	}

	fout<< cont;

	return 0;


}