Cod sursa(job #985179)

Utilizator cont_de_testeCont Teste cont_de_teste Data 16 august 2013 17:50:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
using namespace std;


const int MAX_N = 100100;

struct _graph {
	int v;
	_graph *next;
} *g[MAX_N];

inline void gadd(const int &x, const int &y) {
	_graph *nw = new _graph;
	nw->v = y;
	nw->next = g[x];
	g[x] = nw;
}

int n, m, cc;
bool vis[MAX_N];

inline int dfs(const int &node) {
	vis[node] = true;
	for (_graph *i = g[node]; i; i = i->next) {
		int nw = i->v;
		if (!vis[nw])
			dfs(nw);
	}
}


int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	scanf("%i %i", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%i %i", &x, &y);
		gadd(x, y);
		gadd(y, x);
	}
		
	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			dfs(i), ++cc;
	
	printf("%i\n", cc);
}