Cod sursa(job #2676256)

Utilizator claudiaECiontu Claudia claudiaE Data 23 noiembrie 2020 20:51:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include<fstream>
#include <vector>

using namespace std;
#define MAXN 100005
int N, M;
vector<int> G[MAXN];
char viz[MAXN];
ifstream f("dfs.in");
ofstream g("dfs.out");
void Citeste() {

	f >> N >> M;

	for (int i = 0; i < M; ++i) 
	{
		int x, y;
		f >> x >> y;
		G[x].push_back(y);

		G[y].push_back(x);
	}

}
void DFS(int nod)
{viz[nod] = 1;
	for (vector<int>::iterator i = G[nod].begin(); i != G[nod].end(); ++i)
		if (!viz[*i])
		{
			DFS(*i);
		}
}



void Rezolvare() 
{
	int nr_componente = 0;
	for (int i = 1; i <= N; ++i)
		if (!viz[i]) 
		{
			++nr_componente;
			DFS(i);
		}
     g << nr_componente;

}



int main() {

	Citeste();
	Rezolvare();

}