Cod sursa(job #365125)

Utilizator mottyMatei-Dan Epure motty Data 17 noiembrie 2009 22:09:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<cstdio>
#include<vector>
using namespace std;

const int N=100001;

bool viz[N];

vector <int> v[N];

int n,m,rez;

void read()
{
	int x,y;
	scanf("%d%d",&n,&m);
	for( int i=1 ; i<=m ; ++i )
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

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

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	read();
	for( int i=1 ; i<=n ; ++i )
		if( viz[i]==0 )
		{
			rez++;
			dfs(i);
		}
	printf("%d\n",rez);
	return 0;
}