Cod sursa(job #2231230)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 13 august 2018 15:38:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>

#define MAX_N 100005

using namespace std;

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

int n, m;
vector<int> graf[MAX_N];

bool parcurs[MAX_N] = { false };

void Parcurg(int nod)
{
	if (!parcurs[nod])
	{
		parcurs[nod] = true;

		for (int i = 0; i < graf[nod].size(); i++)
		{
			if (!parcurs[graf[nod][i]])
			{
				Parcurg(graf[nod][i]);
			}
		}
	}
}

int main(void)
{
	int componente = 0;

	fin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int n1, n2;
		fin >> n1 >> n2;

		graf[n1].push_back(n2);
		graf[n2].push_back(n1);
	}

	for (int i = 1; i <= n; i++)
	{
		if (!parcurs[i])
		{
			Parcurg(i);
			componente++;
		}
	}

	fout << componente;

	fin.close();
	fout.close();

	return 0;
}