Cod sursa(job #632910)

Utilizator Alexandru13Dumitraiche Marius-Alexandru Alexandru13 Data 12 noiembrie 2011 15:14:02
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
vector <int> v[100001];
bool vizitati[100001];
void df(int k,int n)
{
	vizitati[k]=true;
	for(int i=1;i<=n;++i)
	{
		if(vizitati[i]==false && v[k][i])
		{
			vizitati[i]=true;
			df(i,n);
		}
	}
}
int main()
{
	int n,m,a,b,nr=0,i;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d\n", &n, &m);
	for(i=1;i<=n;++i)
	{
		scanf("%d %d\n", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(i=1;i<=n;++i)
		if(vizitati[i]==false)
		{
			++nr;
			df(i,n);
		}
	printf("%d",nr);
	return 0;
}