Cod sursa(job #238844)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 3 ianuarie 2009 13:25:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>

using namespace std;

#define NMAX 100100
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define pb push_back

int N, M, Sol;

bitset<NMAX> Viz;
vector <int>  A[NMAX];

void scan(){
	int a, b, i;
#ifndef __ACASA__
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
#endif
	scanf ("%d%d", &N, &M);
	for (i = 1; i <= M; ++i){
		scanf ("%d%d", &a, &b);
		A[a].pb(b);
		A[b].pb(a);
	}
}

void dfs(int x){
	int i;
	Viz[x] = true;
	for (i = 0; i < A[x].size(); ++i)
		if (Viz[A[x][i]] == false)
			dfs(A[x][i]);
}

void solve(){
	int  i;
	for (i = 1; i <= N; ++i)
		if (Viz[i] == false){
			++Sol;
			dfs(i);
		}
}

void print(){
	printf("%d\n", Sol);
	fclose(stdin);
	fclose(stdout);
	exit(0);
}
int main(){
	scan();
	solve();
	print();
}