Cod sursa(job #2792978)

Utilizator izotova_dIzotova Daria izotova_d Data 2 noiembrie 2021 16:52:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.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 top_sort_dfs(int current_node, vector<bool> &visited, stack<int> &stck)
	{
		visited[current_node] = true;

		for (int i = this->adj_list[current_node].size() - 1; i >= 0; i--)
		{
			int neighbour;
			neighbour = adj_list[current_node][i];
			if (!visited[neighbour])
			{
				top_sort_dfs(neighbour, visited, stck);
			}

		}
		stck.push(current_node);
	}

	void topological_sort()
	{
		vector<bool> visited(this->n, false);
		stack<int> stck;

		for (int i = 0; i < this->n; i++)
		{
			if (!visited[i])
			{
				top_sort_dfs(i, visited, stck);
			}
		}

		while (!stck.empty())
		{
			fout << stck.top() + 1 << " ";
			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.topological_sort();

	return 0;
}