Cod sursa(job #2788025)

Utilizator LordNecrateBiowCuciureanu Dragos-Adrian LordNecrateBiow Data 24 octombrie 2021 17:55:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

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


class Graph
{
private:
	bool m_oriented;

	int m_nrNodes;
	int m_nrEdges;
	
	vector <int> m_nodes;
	vector < vector <int> > m_neighborList;

	void BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode = 0);
	void DFS(vector<bool>& visitedNodes, int currentNode = 0);


public:
	Graph(int nrNodes = 0, int nrEdges = 0, bool oriented = false);
	~Graph() {}

#pragma region Getters&Setters
	void setOrientation(bool orientation)
	{
		m_oriented = orientation;
	}
	void setNrNodes(int nrNodes)
	{
		m_nrNodes = nrNodes;
	}
	void setNrEdges(int nrEdges)
	{
		m_nrEdges = nrEdges;
	}

	bool getOrientation()
	{
		return m_oriented;
	}
	int getNrNodes()
	{
		return m_nrNodes;
	}
	int getNrEdges()
	{
		return m_nrEdges;
	}
#pragma endregion

	void buildNeighborList(istream& input);

	vector<int> minimalDistances(int startNode = 0);
	int numberOfConexComponents();
};

Graph::Graph(int nrNodes, int nrEdges, bool oriented)
{
	m_nrNodes = nrNodes;
	m_nrEdges = nrEdges;
	m_oriented = oriented;

	for (int i = 0; i < nrNodes; i++)
	{
		vector <int> emptyVector;
		m_neighborList.push_back(emptyVector);
	}
}

void Graph::buildNeighborList(istream& input) 
{         
	for (int i = 0; i < m_nrEdges; i++) 
	{
		int node1, node2;
		input >> node1 >> node2;

		node1--;
		node2--;

		m_neighborList[node1].push_back(node2);

		if (m_oriented == false) 
		{
			m_neighborList[node2].push_back(node1);
		}
	}
}

void Graph::BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode)
{
	queue<int> nodeOrder;

	nodeOrder.push(startNode);
	distances[startNode] = 0;

	while (nodeOrder.empty() == false)
	{
		int currentNode = nodeOrder.front();
		visitedNodes[currentNode] = true;

		for (auto neighbor : m_neighborList[currentNode])
		{
			if (visitedNodes[neighbor] == false)
			{
				nodeOrder.push(neighbor);
				distances[neighbor] = distances[currentNode] + 1;
				visitedNodes[neighbor] = true;
			}
		}

		nodeOrder.pop();
	}
}

void Graph::DFS(vector<bool>& visitedNodes, int currentNode)
{
	visitedNodes[currentNode] = true;

	for (auto neighbor : m_neighborList[currentNode])
	{
		if (visitedNodes[neighbor] == false)
		{
			DFS(visitedNodes, neighbor);
			visitedNodes[neighbor] = true;
		}
	}
}

vector<int> Graph::minimalDistances(int startNode)
{
	vector <bool> visited(m_nrNodes, false);
	vector <int> distances(m_nrNodes, -1);

	BFS(visited, distances, startNode);

	return distances;
}

int Graph::numberOfConexComponents()
{
	int numberOfConexComponents = 0;

	vector <bool> visited(m_nrNodes, false);

	for (int i = 0; i < m_nrNodes; i++)
	{
		if (visited[i] == false)
		{
			DFS(visited, i);
			numberOfConexComponents++;
		}
	}

	return numberOfConexComponents;
}



int main()
{
	int nrNodes, nrEdges, numberOfConexComponents;

	fin >> nrNodes >> nrEdges;

	Graph graph(nrNodes, nrEdges, false);
	graph.buildNeighborList(fin);

	numberOfConexComponents = graph.numberOfConexComponents();
	fout << numberOfConexComponents;

	fin.close();
	fout.close();

	return 0;
}