Cod sursa(job #914568)

Utilizator xbogdanBogdan Boamfa xbogdan Data 14 martie 2013 11:47:32
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 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 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()
{
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	int n,m;
	int **a;
	in>>n>>m;
	alocare(a,n);
	int x,y;
	for (int i = 0; i < m; ++i)
	{
		in>>x>>y;
		x--;
		y--;
		a[x][y] = 1;
		a[y][x] = 1;
	}
	int *viz = (int*) calloc(n,sizeof(int));
	int nr=0;
	for(int i=0;i<n;i++)
		if(viz[i] == 0)
		{
			parcurgere(i,viz,n,a);
			nr++;
		}
	out<<nr;
	return 0;
}