Cod sursa(job #2839173)

Utilizator ioana__leseLese Ioana ioana__lese Data 25 ianuarie 2022 13:30:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
///LISTE DE ADIACENTA REPREZENTATE CA VECTORI DIN STL
int n, m, nr;
vector<int> A[NMAX]; ///A[x]=un vector din STL care contine lista de adiacenta a lui x

bool viz[NMAX];
void citire();
void DFS(int x);
int main()

{

    int i;
	citire();
	for (i=1; i<=n; i++)
	   if (!viz[i])
	      {
	         nr++;
	         DFS(i);
	      }
	fout<<nr<<'\n';
	return 0;

}

void citire()

{

    int i, x, y;
	fin>>n>>m;
	for (i=0; i<m; i++)

    {
	  fin>>x>>y;
	  A[x].push_back(y);
	  A[y].push_back(x);

    }

}

void DFS(int x)

{
	int i;
	viz[x]=1;
	for (i=0; i<A[x].size(); i++)
	    if (!viz[A[x][i]]) ///vecin nevizitat
	        DFS(A[x][i]);

}