Cod sursa(job #914542)

Utilizator xbogdanBogdan Boamfa xbogdan Data 14 martie 2013 11:32:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include "iostream"
#include "fstream"
#include "cstdlib"
using namespace std;
void alocare(int **&a,int n)
{
	a = (int**)calloc(n,sizeof(int*));
	for(int i=0;i<n;i++)
		a[i] = (int*)calloc(n,sizeof(int));
}
void afisare(int **a,int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cout<<a[i][j]<<" ";
		cout<<"\n";
	}
}
void parcurgere(int p,int *&viz,int n,int **a)
{
	viz[p] = 1;
	for(int i=0;i<n;i++)
		if(a[p][i] == 1 && viz[i] == 0)
			parcurgere(i,viz,n,a);

}
int main(int argc, char const *argv[])
{
	fstream in("dfs.in");
	ofstream out("dfs.out");
	int n,m;
	int **a;
	in>>n>>m;
	alocare(a,n);
	for (int i = 0; i < m; ++i)
	{
		int x,y;
		in>>x>>y;
		a[x][y] = 1;
		a[y][x] = 1;
	}
	int *viz = new int[n];
	int nr=0;
	for(int i=0;i<n;i++)
		if(viz[i] == 0)
		{
			parcurgere(i,viz,n,a);
			nr++;
		}
	out<<nr;
	//afisare(a,n);
	return 0;
}