Cod sursa(job #1692397)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 20 aprilie 2016 19:38:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
typedef struct nod {
	int info;
	nod *next;


}*graf;

graf lda[1000000];
int n, m, j, i, k, x, y;
bool viz[100010];

void add(graf &p, int k) {
	graf h = new nod;
	h->info = k;
	h->next = p;
	p = h;

}

void dfs(int h) {
	viz[h] = 1;
	for (graf r = lda[h]; r != NULL; r = r->next) {
		if (!viz[r->info]) dfs(r->info);
	}

}


int main() {
	fin >> n>>m;
	for (i = 1; i <= m; i++) {
		fin >> x >> y;
		add(lda[x], y);
		add(lda[y], x);
	}
	k = 0;
	for (i = 1; i <= n; i++) {
		if (!viz[i]) {
			k++;
			dfs(i);
		}
	}
	fout << k;

	return 0;
}