Cod sursa(job #2304961)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 18 decembrie 2018 21:26:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>

#define NMAX 100005

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

vector < int > muchii[NMAX];
int uz[NMAX], noduri, n_muchii;

void Read()
{
	in >> noduri >> n_muchii;
	for (int i = 1; i <= n_muchii; i++)
	{
		int x, y;
		in >> x >> y;
		muchii[x].push_back(y);
		muchii[y].push_back(x);
	}
}

void DFS(int nod)
{
	uz[nod] = 1;
	for (int d = 0; d < muchii[nod].size(); d++)
	{
		int nou = muchii[nod][d];
		if (!uz[nou]) DFS(nou);
	}
}

void Solve()
{
	int conex = 0;
	for (int i = 1; i <= noduri; i++)
	if (!uz[i])
	{
		conex++;
		DFS(i);
	}
	out << conex;
}

int main()
{
	Read();
	Solve();
	return 0;
}