Cod sursa(job #629068)

Utilizator bixcabc abc bixc Data 2 noiembrie 2011 16:56:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

#define Nmax 100010

int n, m;
int viz[Nmax];
vector <int> V[Nmax];
stack < pair <int, int> >S;

void DFS (int x) {
	
	int nod, i;
	
	viz[x] = 1;
	for (S.push ( make_pair (x, 0) ); !S.empty ();) {
		
		nod = S.top ().first;
		i = S.top ().second;
		
		while (i < (int)V[nod].size () && viz[V[nod][i]]) i++;
		
		if (i < (int)V[nod].size ()) {
			S.top ().second++;
			viz[ V[nod][i] ] = 1;
			S.push ( make_pair ( V[nod][i], 0 ) );
		}
		else S.pop ();
	}
}

int main () {

	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);

	int x, y;
	
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		V[x].push_back (y);
		V[y].push_back (x);
	}
	
	int sol = 0;
	for (int i = 1; i <= n; i++)
		if (viz[i] == 0) sol++, DFS (i);
	
	printf ("%d", sol);
	
}