Cod sursa(job #199718)

Utilizator LuxOccultaRadu Dolea LuxOcculta Data 20 iulie 2008 12:09:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
using namespace std;

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

/*
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);
	}
}	
*/
void bf(int x,int n,int *a[N],bool viz[N])
{
	int coada[N],p=0,u=0,i,y;
	//pun varful initial in coada
	coada[u++]=x;
	viz[x]=true;
	while(p!=u){//cat timp coada nu e vida
		x=coada[p++];//scot din coada varful accesibil
		for(i=1;i<=a[x][0];++i)//parcurg vecinii sai
		{
			y=a[x][i];//vecinul curent (cu nr de ordine i)
			if(!viz[y])//daca nu a fost vizitat
			{
				coada[u++]=y;//il pun in coada
				viz[y]=true;
			}
		}
	}
}
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);
			bf(i,n,a,viz);
			++nr;
		}
	g<<nr<<"\n";
	ff.close();
	g.close();
	return 0;
}