Cod sursa(job #2839165)

Utilizator gabrieldima6543DIMA GABI gabrieldima6543 Data 25 ianuarie 2022 13:26:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#define NMAX 100004

using namespace std;

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

int n, m, start, aux = 0;
vector<int> A[NMAX];
///A[x] este un vector din stl care contine lista de adiacenta a lui x

bool viz[NMAX];

void citire();
void DFS(int x);

int main()
{
	int j;
	citire();
	for (j = 1; j <= n; j++)
	{
		if (viz[j] == 0)
		{
			aux++;
			DFS(j);
		}
	}
	fout << aux;
	return 0;
}

void citire()
{
	int i, x, y;
	fin >> n >> m;
	for (i = 0; i < m; i++)
	{
		fin >> x >> y;
		///adaug pe y in lista de adiacenta a lui x
		///1, 2, 3, ..., d[x]-1
		A[x].push_back(y);
		///adaug pe x in linia de adiacenta a lui y
		A[y].push_back(x);
	}
}

void DFS(int x)
{
	int i;
	///vizitez vf x
	viz[x] = 1;
	///parcurg vecinii lui x
	for (i = 0; i < A[x].size(); i++)
	{
		if (!viz[A[x][i]]) /// x si i sunt vf adiacente si i nevizitat
			DFS(A[x][i]);
	}
}