Cod sursa(job #779941)

Utilizator crushackPopescu Silviu crushack Data 19 august 2012 15:57:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#include <vector>
#define NMax 100010
using namespace std;

const char IN[]="dfs.in",OUT[]="dfs.out";

int N,M,Rez;
bool b[NMax];
vector<int> ad[NMax];

void dfs(int x){
	b[x]=true;
	for (int i=0;i<(int)ad[x].size();++i) if (!b[ad[x][i]])
		dfs(ad[x][i]);
}

int main()
{
	int i,x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	while (M--)
	{
		scanf("%d%d",&x,&y);
		ad[x].push_back(y);
		ad[y].push_back(x);
	}
	fclose(stdin);

	for (i=1;i<=N;++i) if (!b[i]){
		++Rez;
		dfs(i);
	}

	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);

	return 0;
}