Cod sursa(job #199424)

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

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


void df(int x,int n,int a[N][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][N],x,y;
	bool viz[N];
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	f>>n>>m;
	for(i=1;i<=n;++i){
		viz[i]=false;
		a[i][0]=0;
	}
	for(i=1;i<=m;++i)
	{
		f>>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";
	f.close();
	g.close();
	return 0;
}