Cod sursa(job #855505)

Utilizator catlSorlei Maria catl Data 15 ianuarie 2013 00:35:25
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
using namespace std;
#include<cstdio>
#include<vector>
vector<int>v[100005];
int vazut[100005];
void dfs(int nod){
	vazut[nod]=1;
	for(int i=0;i<v[nod].size();i++)
		if(!vazut[v[nod][i]])
			dfs(v[nod][i]);
}
int main(void){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int n,m,nr=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int n1=1;
	while(n1<=n){
		if(vazut[n1]==0)
			dfs(n1);
		n1=1;
		while(vazut[n1]==1)
			n1++;
		nr++;
	}
	printf("%d",nr);
	return 0;
}