Cod sursa(job #369197)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 27 noiembrie 2009 15:24:07
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
using namespace std;
#include<fstream>
int n,m;
short lista[1001][1001],conex[1000];
void read()
{
	int x,y,i;
	ifstream fin("dfs.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		lista[x][++lista[x][0]]=y;
	}
	fin.close();
}
void dfs(int x,int c)
{
	int i,y,n=lista[x][0];
	conex[x]=c;
	for(i=1;i<=n;i++)
	{
		y=lista[x][i];
		if(conex[y]==0)
		{
			conex[y]=c;
			dfs(y,c);
		}
	}
			
}
void write(int n)
{
	ofstream fout("dfs.out");
	fout<<n;
	fout.close();
}
int main()
{
	int i,nrc=0;
	read();
	for(i=1;i<=n;i++)
		if(conex[i]==0)
	      dfs(i,++nrc);
	write(nrc);
	return 0;
}