Cod sursa(job #591922)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 25 mai 2011 21:01:04
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
# include <fstream>
# define dim 10002

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int a[dim][dim],n,m;
int viz[dim];
int x,y;
long sol;

void citire()
{
	int i;
	f >> n >> m;
	for( i = 1 ; i <= m ; i ++ )
	{
	 f >> x>> y;
		a[x][0]++;
		a[x][a[x][0]] = y;
		a[y][0]++;
		a[y][a[y][0]] = x;
	}
}

void dfs(int x)
{
	int i;
	viz[x] = 1;
	for(i = 1;i <= a[x][0]; i++)
		if(viz[a[x][i]] == 0)
			dfs(a[x][i]);
}

void rezolva()
{
	int i;
	
	for( i = 1 ; i <= n ; ++ i)
		if(viz[i] == 0)
		{
			dfs(i);
			sol ++;
		}
		g<<sol;
}

int main()
{
	citire();
	rezolva();
	return 0;
}