Cod sursa(job #388992)

Utilizator victor_bla_blaDumitrescu Victor victor_bla_bla Data 31 ianuarie 2010 16:43:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<list>
#define AMAX 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
long /*a[AMAX][AMAX], */vz[AMAX],i,n,m,x,y,cc;
struct lista {long nv; list<long> L;} v[AMAX];
void dfs(int);
int main()
{
	fin>>n>>m;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y;
		v[x].nv++;//a[x][0]++;
		v[y].nv++;//a[y][0]++;
		v[x].L.push_back(y);//a[x][a[x][0]]=y;
		v[y].L.push_back(x);//a[y][a[y][0]]=x;
	}
	for (i=1;i<=n;i++)
		if (!vz[i])
		{
			dfs(i);
			cc++;
		}
fout<<cc;
return 0;}
void dfs(int x)
{//int i;
	list<long>::iterator i;
	vz[x]=1;
	/*for (i=1;i<=a[x][0];i++)
		if (!vz[a[x][i]]) 
			dfs(a[x][i]);*/
	for (i=v[x].L.begin();i!=v[x].L.end();i++)
		if (!vz[*i])
			dfs(*i);
}