Cod sursa(job #559506)

Utilizator ursu-valiJerdea Florin ursu-vali Data 17 martie 2011 21:14:48
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<vector>
#define infile "dfs.in"
#define outfile "dfs.out"
#define nod 100010

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];

vector <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;
}