Cod sursa(job #2788086)

Utilizator LordNecrateBiowCuciureanu Dragos-Adrian LordNecrateBiow Data 24 octombrie 2021 21:39:45
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.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);
	void BCDFS(vector< vector <int>>& bcc, stack<int>& nodeStack, vector<bool>& visited, vector<int>& depth, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int currentDepth);


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

#pragma region Setters&Getters
	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();
	vector< vector <int> > BiconnectedComponents();
};

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;
		}
	}
}

void Graph::BCDFS(vector< vector <int>>& bcc, stack<int>& nodeStack, vector<bool>& visited, vector<int>& depth, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int currentDepth)
{
	depth[currentNode] = currentDepth;
	lowestDepthReacheable[currentNode] = currentDepth;
	visited[currentNode] = true;
	nodeStack.push(currentNode);

	for (auto neighbor : m_neighborList[currentNode])
	{
		if (neighbor != parentNode)
		{
			if (visited[neighbor] == true)
			{
				lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], depth[neighbor]);
			}
			else
			{
				BCDFS(bcc, nodeStack, visited, depth, lowestDepthReacheable, neighbor, currentNode, currentDepth + 1);

				lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], lowestDepthReacheable[neighbor]);

				if (depth[currentNode] <= lowestDepthReacheable[neighbor])
				{
					vector <int> biconnectedComponent;
					biconnectedComponent.push_back(currentNode);

					int node = nodeStack.top();
					nodeStack.pop();
					biconnectedComponent.push_back(node);

					while (node != neighbor)
					{
						node = nodeStack.top();
						nodeStack.pop();
						biconnectedComponent.push_back(node);
					}

					bcc.push_back(biconnectedComponent);
				}
			}
		}
	}
}

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;
}

vector< vector <int> > Graph::BiconnectedComponents() 
{
	vector< vector<int> > bcc;

	stack<int> nodeStack;

	vector<bool> visited(m_nrNodes, false);
	vector<int> depth(m_nrNodes, -1);
	vector<int> lowestDepthReacheable(m_nrNodes, -1);

	BCDFS(bcc, nodeStack, visited, depth, lowestDepthReacheable, 0, -1, 0);

	return bcc;
}



int main()
{
	int nrNodes, nrEdges;
	vector< vector<int> > bcc;

	fin >> nrNodes >> nrEdges;

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

	bcc = graph.BiconnectedComponents();

	fout << bcc.size() << "\n";

	for (int i = 0; i < bcc.size(); i++)
	{
		for (auto node : bcc[i])
		{
			fout << node << " ";
		}
		fout << "\n";
	}

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

	return 0;
}