Cod sursa(job #2335014)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 3 februarie 2019 14:47:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
typedef unsigned int uint;

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

class Graph
{
	uint V;
	vector<vector<uint>> adj;
	void DFS(uint node, vector<bool> &v);
public:
	Graph(const uint V);
	void Add_edge(uint x, uint y);
	uint NrOfComps();
};

Graph::Graph(const uint V)
{
	this->V = V;
	adj.assign(V + 1, vector<uint>());
}

void Graph::Add_edge(uint x, uint y)
{
	adj[x].emplace_back(y);
	adj[y].emplace_back(x);
}

void Graph::DFS(uint node, vector<bool> &v)
{
	v[node] = true;
	for (auto &i : adj[node])
	{
		if (!v[i])
			DFS(i,v);
	}
}

uint Graph::NrOfComps()
{
    uint nr = 0;
	vector<bool> v(V + 1, false);

	for (uint i = 1; i <= V; ++i)
	{
		if (!v[i])
		{
		    ++nr;
		    DFS(i,v);
		}
	}

	return nr;
}

int main()
{
	uint n,m;
	fin >> n >> m;

	Graph G(n);

	for (uint x,y, i = 0; i < m; ++i)
	{
		fin >> x >> y;
		G.Add_edge(x,y);
	}

	fout << G.NrOfComps();
}