Cod sursa(job #2743893)

Utilizator muiepulicimatacutactu muiepulici Data 23 aprilie 2021 17:14:09
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>

struct NOD {
	int v;
	NOD* urm;
};

NOD* noduri[100001];

void Add(NOD*& dest, int Y) {
	NOD* nod = new NOD();
	nod->v = Y;
	nod->urm = dest;
	dest = nod;
}

int N, M, X, Y;
int v[100001];

void DFS(int k) {
	v[k] = 1;

	NOD* nod = noduri[k];

	while (nod) {
		if (v[nod->v] == 0)
			DFS(nod->v);

		nod = nod->urm;
	}
}

int main() {
	std::ifstream fin("dfs.in");
	std::ofstream fout("dfs.out");

	fin >> N >> M;

	for (int i = 0; i < M; ++i) {
		fin >> X >> Y;
		Add(noduri[X], Y);
	}

	fin.close();

	int nrc = 0;

	for (int i = 1; i <= N; ++i) {
		if (v[i] == 0) {
			++nrc;
			DFS(i);
		}
	}

	fout << nrc;

	fout.close();

	return 0;
}