Cod sursa(job #283401)

Utilizator mihneadbDobrescu-Balaur Mihnea mihneadb Data 19 martie 2009 09:16:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector < bool > viz(100100);
int n,m,nr[100100];
vector < int > g[100100];

void citire(){
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a,&b);
		g[a].push_back (b);
		g[b].push_back (a);
		nr[a]++;
		nr[b]++;
	}
}

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

int check(){
	int i,c=0;
	for(i=1;i<=n;++i)
		if(!viz[i]){
			c++;
			df(i);
		}
	return c;
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	printf("%d\n",check());
	return 0;
}