Cod sursa(job #2792939)

Utilizator izotova_dIzotova Daria izotova_d Data 2 noiembrie 2021 15:50:01
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
//Graph class, all the nodes start from 0
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 sccdfs(int current_node, int &id, stack<int> &stck, vector<bool> &on_stack, vector<int> &ids, vector<int> &low_link_values, vector<vector<int>> &str_con_comps)
	{
		stck.push(current_node);
		on_stack[current_node] = true;
		ids[current_node] = id;
		low_link_values[current_node] = id;
		id++;

		for (unsigned int i = 0; i < this->adj_list[current_node].size(); i++)
		{
			int neighbour;
			neighbour = adj_list[current_node][i];

			if (ids[neighbour] == -1)
			{
				sccdfs(neighbour, id, stck, on_stack, ids, low_link_values, str_con_comps);
			}
			if (on_stack[neighbour])
			{
				low_link_values[current_node] = min(low_link_values[current_node], low_link_values[neighbour]);
			}
		}

		if (ids[current_node] == low_link_values[current_node])
		{
			vector<int> str_con_comp;
			int node = stck.top();
			while (node != current_node)
			{
				str_con_comp.push_back(node);
				stck.pop();
				on_stack[node] = false;
				low_link_values[node] = ids[current_node];
				node = stck.top();
			}
			str_con_comp.push_back(current_node);
			stck.pop();
			
			str_con_comps.push_back(str_con_comp);
		}

	}

	void strongly_connected_components()
	{
		//used to give each node an id
		int id = 0;
		int scc_count;

		vector<int> ids(this->n, -1);
		vector<int> low_link_values(this->n, 0);
		vector<bool> on_stack(this->n, false);
		stack<int> stck;
		vector<vector<int>> str_con_comps;

		for (int i = 0; i < this->n; i++)
		{
			if (ids[i] == -1)
			{
				sccdfs(i, id, stck, on_stack, ids, low_link_values, str_con_comps);
			}
		}
		
		if (!stck.empty())
		{
			scc_count = stck.size() + str_con_comps.size();
		}
		else
		{
			scc_count = str_con_comps.size();
		}

		fout << scc_count << "\n";
		for (unsigned int i = 0; i < str_con_comps.size(); i++)
		{
			for (unsigned int k = 0; k < str_con_comps[i].size(); k++)
			{
				fout << str_con_comps[i][k] + 1 << " ";
			}
			fout << "\n";
		}
		while (!stck.empty())
		{
			int nd = stck.top();
			fout << nd + 1 << "\n";
			stck.pop();
		}
		

	}

};



int main()
{
	//number of nodes
	int N;
	//number of edges
	int E;

	fin >> N >> E;
	Graph graph(N, true);
	int n1, n2;
	for (int i = 0; i < E; i++)
	{
		fin >> n1 >> n2;
		graph.add_edge(n1 - 1, n2 - 1);
	}
	graph.strongly_connected_components();

	return 0;
}