Cod sursa(job #348546)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 16 septembrie 2009 00:11:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define fin  "dfs.in"
#define fout "dfs.out"

#define mp make_pair
#define pb push_back

#define NMAX 100010

int N, M, cnt;
char viz[NMAX];
vector<int> g[NMAX];

void df(int x)
{
	viz[x] = 1;
	for ( int i = 0; i < g[x].size(); ++i )
		if ( !viz[ g[x][i] ] )
			df(g[x][i]);
}

int main()
{
	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%d%d",&N,&M);

	memset(viz,0,sizeof(viz));
	for ( int i = 1; i <= M; ++i )
	{
		int a, b;
		scanf("%d%d",&a,&b);
		g[a].pb(b);
		g[b].pb(a);
	}

	for ( int i = 1; i <= N; ++i )
		if ( !viz[i] ) df(i), ++cnt;

	printf("%d\n",cnt);

	return 0;
}