Cod sursa(job #559499)

Utilizator ursu-valiJerdea Florin ursu-vali Data 17 martie 2011 21:10:33
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
//#include<list>
#define infile "dfs.in"
#define outfile "dfs.out"
#define nod 20001

//using namespace std;
long n,m,nr;
long nrv[nod];//numarul vecinilor lui i;
long viz[nod];//nodul i face parte sau nu dintrun subgraf conex
long a[nod][nod];

//list <long> lista[nod];

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

void dfs(long k)
{
	long i,vecin;
	viz[k]=1;
	for(i=0;i<nrv[k];i++)
	{
		//vecin=lista[k][i];
		vecin=a[k][i];
		if(!viz[vecin])
			dfs(vecin);
	}
}

void afisare()
{
	printf("%ld",nr);
}
int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	citire();
	for(int i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			nr++;
			dfs(i);
		}
	}
	afisare();
	fclose(stdin);
	fclose(stdout);
	return 0;
}