Cod sursa(job #1820344)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 1 decembrie 2016 16:42:20
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MaxN = 100000;
vector<int> G[MaxN];
int n,m,sol;
bool v[MaxN];

void ReadGraph();
void Df(int x);


int main()
{
	ReadGraph();
	for(int z=1;z<=n;z++)
	if(v[z]==0) Df(z),sol++;

	fo<<sol;

}

void ReadGraph()
{
	int x, y;
	fi >> n >> m;

	while ( fi >> x >> y)
	{
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void Df(int x)
{
	v[x] = true;
	for (const int& y : G[x])
		if ( !v[y] )
			Df(y);
}


//void Df(int x)
//{
//	v[x] = true;
//
//	for (auto it = G[x].begin(); it != G[x].end(); ++it)
//	{
//		if ( v[*it] )
//			continue;
//		Df(*it);
//	}
//}


//void Df(int x)
//{
//	v[x] = true;
//
//	for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
//	{
//		if ( v[*it] )
//			continue;
//		Df(*it);
//	}
//}


//void Df(int x)
//{
//	v[x] = true;
//
//	for (size_t i = 0; i < G[x].size(); ++i)
//	{
//		int y = G[x][i];
//		if ( v[y] )
//			continue;
//		Df(y);
//	}
//}