Cod sursa(job #389338)

Utilizator cezyGrigore Cezar cezy Data 1 februarie 2010 14:34:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<vector>
using namespace std;
#define MAXN 200005
int n,m,x,k=0;
vector <int> v[MAXN];
int cost[MAXN],s[MAXN],g[MAXN];
void citire ()
{
	ifstream fin("dfs.in");
	fin>>n>>m;
	int i,a,b;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(i=1;i<=n;i++)
		g[i]=v[i].size();
	fin.close();
}
void bfs(int nod)
{
	int i,l=1,j;
	
	cost[nod]=0;
	s[l]=nod;
	for(i=1;i<=l;i++)
		for(j=0;j<g[s[i]];j++)
		{
			if(cost[v[s[i]][j]]==-1)
			{
				s[++l]=v[s[i]][j];
				cost[s[l]]=cost[s[i]]+1;
			}
		}
}
int main ()
{
	citire();
	int i;
	memset(cost,-1,sizeof(cost));
	ofstream fout("dfs.out");
	for(i=1;i<=n;i++)
		if(cost[i]==-1)
		{
			bfs(i);
			k++;
		}
	fout<<k;
	fout.close();
	return 0;
}