Cod sursa(job #833278)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 12 decembrie 2012 10:46:33
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

vector <int> vec[100000];

int n,m;
int viz[100006];

void citeste()
{
	int a,b;
	in>>n>>m;
	for (int i=1;i<=m;i++)
	{
		in>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
}
void initializeaza()
{
	for (int i=1;i<=n;i++)
		viz[i]=0;
}


void parc(int nod)
{	int i;
	viz[nod]=1;
	for ( i=0;i<vec[nod].size();i++)
	{
		if  ( !viz[vec[nod][i]] )
		parc(vec[nod][i]);
	}
}

int main()
{
	citeste();
	initializeaza();
	int nr=1;
	int i=1;
	parc(1);
	while (i<=n)
	{
		if (viz[i]==1) i++;
		else
		{	parc(i);
			nr++;
		}
	}
	out<<nr;

	return 0;
}