Cod sursa(job #2792535)

Utilizator izotova_dIzotova Daria izotova_d Data 1 noiembrie 2021 20:57:10
Problema Componente biconexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

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


class Graph
{
private:
	//number of nodes
	int n;
	//number of edges
	int e;
	//bool if graph is oriented
	bool oriented;
	//adj list for graph representation
	vector<vector<int>> adj_list;
public:

	Graph(int n, bool oriented)
	{
		this->n = n;
		this->e = 0;
		this->oriented = oriented;
		//populate adj list with empty vectors
		vector<int> empty;
		for (unsigned int i = 0; i < n; i++)
		{
			this->adj_list.push_back(empty);
		}
	}
	virtual ~Graph() {}

	void add_edge(int node1, int node2)
	{
		this->e++;
		this->adj_list[node1].push_back(node2);

		//if graph is not oriented, then push from the second node
		if (!this->oriented)
		{
			this->adj_list[node2].push_back(node1);
		}
	}

	void find_biconnected_comp(int current_node, int parent_node, int current_distance, 
		vector<int>& distance, vector<int>& shortest_distance, vector<bool>& visited, vector<int>& nodes, vector<vector<int>>& bicon_comps)
	{
		distance[current_node] = current_distance;
		shortest_distance[current_node] = current_distance;
		visited[current_node] = true;
		nodes.push_back(current_node);

		for (unsigned int i = 0; i < this->adj_list[current_node].size(); i++)
		{
			int next_node;
			next_node = this->adj_list[current_node][i];
			if (next_node != parent_node)
			{
				if (!visited[next_node])
				{
					find_biconnected_comp(next_node, current_node, current_distance + 1, distance, shortest_distance, visited, nodes, bicon_comps);

					shortest_distance[current_node] = min(shortest_distance[current_node], shortest_distance[next_node]);

					if (distance[current_node] <= shortest_distance[next_node])
					{
						/*
						if the distance of current node is smaller than or equal
						to the shortest distance of the next node,
						that means, that the current node is an articulation point

						push all the components from nodes to bicon_comp
						while popping the nodes
						untill we reach the articulation point
						*/
						vector<int> bicon_comp;
						bicon_comp.push_back(current_node);

						while (nodes.back() != current_node)
						{
							bicon_comp.push_back(nodes.back());
							nodes.pop_back();
						}

						bicon_comps.push_back(bicon_comp);

					}
				}
				else
				{
					
					//modify the shortest distance if the node is already visited
					shortest_distance[current_node] = distance[next_node];
				}
			}

		}
	}

	void biconnected_components()
	{
		//setting up all the vectors
		vector<vector<int>> bicon_comps;
		vector<int> nodes;
		vector<bool> visited;
		vector<int> distance;
		vector<int> shortest_distance;

		for (unsigned int i = 0; i < this->n; i++)
		{
			visited.push_back(false);
			distance.push_back(-1);
			shortest_distance.push_back(-1);
		}

		find_biconnected_comp(0, -1, 0, distance, shortest_distance, visited, nodes, bicon_comps);

		fout << bicon_comps.size() << endl;

		for (unsigned int i = 0; i < bicon_comps.size(); i++)
		{
			for (unsigned int k = 0; k < bicon_comps[i].size(); k++)
			{
				fout << bicon_comps[i][k] << " ";
			}

			fout << endl;
		}
	}


};



int main()
{
	//number of nodes
	int N;
	//number of edges
	int E;
	fin >> N >> E;
	Graph graph(N, false);
	int n1, n2;
	for (int i = 0; i < E; i++)
	{
		fin >> n1 >> n2;
		graph.add_edge(n1-1, n2-1);
	}
	graph.biconnected_components();
	return 0;
}