Cod sursa(job #2797073)

Utilizator vasiliumirunamariaVasiliu Miruna-Maria vasiliumirunamaria Data 9 noiembrie 2021 11:06:44
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define N 100005
using namespace std;

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


bool viz[N];
stack <int> S;
//vector <int> c[N];

class Graph {


public:
	int n; //nr de varfuri
	int m; //nr de muchii

	vector <int> a[N];
	//vector <int> a_t[N];



	Graph(int n, int m)
	{
		this->n = n;
		this->m = m;
	}
	void Citire_orientat()
	{
		int i;
		int x, y;

		for (i = 0; i < m; i++)
		{
			fin >> x >> y;
			a[x].push_back(y);
			//a_t[y].push_back(x);

		}

	}

	void DFS(int x);
	void DFS_T(int x, int ct);
	void CompTConexe();
	void ParcurgereGraf();
	void SortTop();
	


};

void Graph::ParcurgereGraf()
{
	int i;
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS(i);
}

void Graph::DFS(int x)
{
	int i;
	viz[x] = 1;
	for (i = 0; i < a[x].size(); i++)
		if (!viz[a[x][i]])
			DFS(a[x][i]);
	S.push(x);
}
void Graph::SortTop()
{
	int i;
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS(i);
	while (!S.empty())
	{
		cout << S.top() << " ";
		S.pop();
	}
}

/*
void Graph::DFS_T(int x,int ct)
{
	int i;
	viz_t[x] = 1;
	c[ct].push_back(x); //pt fiecare nod, din ce comp tconexa face parte
	for (i = 0; i < a_t[x].size(); i++)
		if (viz_t[a_t[x][i]] == 0)
			DFS_T(a_t[x][i], ct);
}

void Graph::CompTConexe()
{
	int i, j, x, ct = 0;
	while (!S.empty())
	{
		x = S.top();
		S.pop();
		if (viz_t[x] == 0)
		{
			ct++;
			DFS_T(x, ct);
		}

	}
	fout << ct << "\n";
	for (i = 1; i <= ct; i++)
	{
		for (j = 0; j < c[i].size(); j++)
			
				fout << c[i][j] << " ";
		fout << "\n";
	}

}
*/

int main()
{
	int n, m;

	fin >> n >> m;
	Graph g(n, m);
	g.Citire_orientat();
	g.SortTop();
	
	//g.ParcurgereGraf();
	//g.CompTConexe();
	






	return 0;
}