Cod sursa(job #694574)

Utilizator ursu-valiJerdea Florin ursu-vali Data 27 februarie 2012 21:52:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#include<vector>
#define infile "dfs.in"
#define outfile "dfs.out"
#define nmax 100002
using namespace std;
long n,m;
long ok[nmax]; //nodul i face parte sau nu dintr-un subgraf conex
long nrv[nmax]; //numarul vecinilor lui i
long nr;

vector <long> lista[nmax];

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

void dfs(long x)
{
	ok[x]=1;
	int vecin;
	for(int i=0;i<nrv[x];i++)
	{
		vecin=lista[x][i];
		if(!ok[vecin])
			dfs(vecin);
	}
}
int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	read();
	nr=0;
	for(int i=1;i<=n;i++)
		if(!ok[i])
		{
			dfs(i);
			nr++;
		}
	printf("%ld\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}