Cod sursa(job #233008)

Utilizator mihnea_andreiMihnea Andrei mihnea_andrei Data 16 decembrie 2008 18:38:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream> 

using namespace std; 

const int N=100005; 

bool viz[N]; 
int *a[N]; 
int x,y,n,m,d[N];

ofstream out("dfs.out");

void citire () 
{ 
	ifstream in("dfs.in"); 
	in>>n>>m; 
	while(m--) 
	{ 
		in>>x>>y; 
		d[x]++; 
		d[y]++; 
	} 
	in.close ();
} 

void aloc () 
{ 
	for(int i=1;i<=n;i++) 
	{ 
		a[i]=new int[1+d[i]]; 
		a[i][0]=0; 
	} 
}

void completez () 
{ 
	ifstream in2("dfs.in"); 
	in2>>n>>m; 
	while(m--) 
	{ 
		in2>>x>>y; 
		a[x][++a[x][0]]=y; 
		a[y][++a[y][0]]=x; 
	} 
	in2.close(); 
} 

/*void afisare () 
{ 
	for(int i=1;i<=n;i++) 
	{ 
		out<<i<<": "; 
		for(int j=1;j<=a[i][0];j++) 
			out<<a[i][j]<<" ";
		out<<"\n";
	} 
} 
*/
void dfs (int x) 
{ 
	viz[x]=true;
	for(int i=1;i<=a[x][0];i++) 
	{ 
		y=a[x][i]; 
		if(viz[y]==false) 
			dfs(y); 
	} 
}
int numar ()
{ 
	int nr=0;
	for(int i=1;i<=n;i++) 
	{
		if(viz[i]==false) 
		{ 
			dfs(i); 
			nr++;
		} 
	} 
	return nr;
}

int main () 
{ 
	citire (); 
	aloc (); 
	completez (); 
	//afisare (); 
	out<<numar();
	out.close ();
	return 0; 
}