Cod sursa(job #2532260)

Utilizator RobysenLazarov Robert Robysen Data 27 ianuarie 2020 17:16:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

#define nMax 100000

int n, m, viz[nMax + 5], components;

typedef struct node {
	int value;
	node *next;
} *myNode;
myNode arb[nMax + 5];

void add(int val, myNode &target) {
	myNode element;
	element = new node;
	element -> value = val;
	element -> next = target;
	target = element;	
}

void read() {
	in >> n >> m;
	int x, y;
	for (int i = 1; i <= m; i++) {
		in >> x >> y;
		add(y, arb[x]);
		add(x, arb[y]);
	}
}

void depth(int i) {
	myNode k;
	viz[i] = 1;
	for (k = arb[i]; k != NULL; k = k -> next) {
		if (!viz[k -> value]) depth(k -> value);
	}
}

int main() {
	read();
	int i;
	for (i = 1; i <= n; i++) {
		if (!viz[i]) {
			components++;
			depth(i);
		}
	}
	out << components;
}