Cod sursa(job #1884702)

Utilizator ClaudiuHHiticas Claudiu ClaudiuH Data 19 februarie 2017 01:11:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
//Parcurgerea in Adancime
#include <fstream>
#include <vector>
using namespace std;

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

using VI = vector<int>;
vector<VI> G;  //  G[x] : lista de vecini ai nodului x
vector<bool> s;
int n, m;

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

int main()
{
	int cnt = 0;
	ReadGraph();
	for(int i = 1; i <= n; ++i)
		if(!s[i])
		{
			cnt++;
			Df(i);
		}
	fout << cnt;
}

void Df(int x)
{
	s[x] = true;
	//fout << x << ' ';
	for (const int& y : G[x])
		if (!s[y] )
			Df(y);
}

/*
void Df(int x)
{
	s[x] = true;
	fout << x << ' ';
	for (size_t i = 0;  i < G[x].size(); ++i)
		if (!s[G[x][i]])
			Df(G[x][i]);
	
}
*/ 
/*
void Df(int x)
{
	s[x] = true;
	fout << x << ' ';
	
	for (auto it = G[x].begin(); it != G[x].end(); ++it)
		if (!s[*it])
			Df(*it);
	
}
*/ 
/*
void Df(int x)
{
	s[x] = true;
	fout << x << ' ';
	
	for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
		if (!s[*it])
			Df(*it);
	
}
*/
void ReadGraph()
{
	int x, y;
	fin >> n >> m;
	
	G = vector<VI>(n + 1);
	s = vector<bool>(n + 1);
	
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
}