Cod sursa(job #2426675)

Utilizator TheShark62FMI Cristian-Andrei Ionescu TheShark62 Data 29 mai 2019 00:52:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<list>

using namespace std;

unsigned int n, m;
list<unsigned int> listaAdj[100001];
bool viz[100001];

void citire() {
	ifstream in("dfs.in");

	in >> n >> m;
	for (int i = 0; i < m; i++) {
		unsigned int x, y;
		in >> x >> y;
		listaAdj[x].push_back(y);
		listaAdj[y].push_back(x);
	}
	in.close();
}

void dfs(unsigned int x) {
	viz[x] = true;

	for (unsigned int i : listaAdj[x])
		if (!viz[i])
			dfs(i);
}

int main() {
	citire();

	unsigned int nrCompConexe = 0;
	for (unsigned int i = 1; i <= n; i++)
		if (!viz[i]) {
			++nrCompConexe;
			dfs(i);
		}

	ofstream out("dfs.out");
	out << nrCompConexe;
	out.close();

	return 0;
}