Cod sursa(job #2792556)

Utilizator izotova_dIzotova Daria izotova_d Data 1 noiembrie 2021 21:38:36
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.36 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 (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])
					{
						
						vector<int> bicon_comp;
						bicon_comp.push_back(current_node);
						int node = nodes.back();
						nodes.pop_back();
						bicon_comp.push_back(node);

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

						bicon_comps.push_back(bicon_comp);

					}
				}
				else
				{
					
					//modify the shortest distance if the node is already visited
					shortest_distance[current_node] = min(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 (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] + 1 << " ";
			}

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