Cod sursa(job #199426)

Utilizator LuxOccultaRadu Dolea LuxOcculta Data 18 iulie 2008 19:17:50
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
using namespace std;

#include <iostream>
#include <fstream>
const int N=10005;


void df(int x,int n,int *a[N],bool viz[N])
{
	viz[x]=true;
	for(int i=1;i<=a[x][0];++i)
	{
		int y=a[x][i];
		if(!viz[y])
			df(y,n,a,viz);
	}
}	

int main()
{
	int nr=0,n,m,i,*a[N],x,y;
	int d[N]={0};
	bool viz[N];
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		++d[x];
		++d[y];
		//a[x][++a[x][0]]=y;
		//a[y][++a[y][0]]=x;
	}
	f.close();
	for(i=1;i<=n;++i){
		viz[i]=false;
		a[i]=new int[1+d[i]];
		a[i][0]=0;
	}
	ifstream ff("dfs.in");
	ff>>n>>m;
	for(i=1;i<=m;++i)
	{
		ff>>x>>y;
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
	for(i=1;i<=n;++i)
		if(!viz[i]){
			df(i,n,a,viz);
			++nr;
		}
	g<<nr<<"\n";
	ff.close();
	g.close();
	return 0;
}