Cod sursa(job #2676252)

Utilizator claudiaECiontu Claudia claudiaE Data 23 noiembrie 2020 20:39:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 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 ReadData() {

	f >> N >> M;

	for (int i = 0; i < M; ++i) {

		int a, b;

		f >> a >> b;



		G[a].push_back(b);

		G[b].push_back(a);

	}

}



void DF(int nod) {

	viz[nod] = 1;

	for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)

		if (!viz[*it])

		{
			DF(*it);
		}


}



void Solve() {

	int componente = 0;

	for (int i = 1; i <= N; ++i)

		if (!viz[i]) {

			++componente;

			DF(i);

		}

	g << componente;

}



int main() {

	ReadData();

	Solve();

}