Cod sursa(job #2683467)

Utilizator Un.wiseApetrei George Un.wise Data 11 decembrie 2020 14:34:08
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

int N, M, X, Y,cnt;
int viz[100005];

struct nod {
	int x;
	nod* next;
};

 nod* v[100005];

void add(nod*& dest, int val){
	nod* p;
	p = new nod;
	p->x = val;
	p->next = dest;
	dest = p;
}


void DFS(int curentNod) {
	nod* p;
	viz[curentNod] = 1;

	for ( p = v[curentNod]; p != NULL; p = p->next)
		if (!viz[p->x])
			DFS(p->x);

}

int main() {

	in >> N >> M;

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

		in >> X >> Y;
		add(v[X], Y);
		add(v[Y], X);
	}

	for (int i = 1; i <= N; i++) 
		if (!viz[i]) { cnt++; DFS(i); }

	out << cnt;

	in.close();
	out.close();
	return 0;
}