Cod sursa(job #2793726)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 3 noiembrie 2021 22:24:46
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <list>
#include <queue>
#include <stack>

using namespace std;

ifstream f("sortaret.in");
ofstream o("sortaret.out");

class Graf {
	int noduri, muchii;
	unordered_map<int, list<int>>vecini;
	unordered_map<int, bool> vizitat;
	stack<int>stiva_sortare_topologica;


public:
	Graf(int n, int m);
	int get_noduri();
	int get_muchii();
	int get_vizitat(int nod);
	void adauga_muchie_neorientat(int nod1, int nod2);
	void adauga_muchie_orientat(int nod1, int nod2);
	void sorteaza();
	void dfs(int nod);
	void componente_conexe();
	void bfs(int nod);
	void sortare_topologica();
	void tool_sortare_topologica(int nod);
};

Graf::Graf(int n, int m)
{
	this->noduri = n;
	this->muchii = m;
	for (int i = 1; i <= n; i++)
		vizitat[i] = 0;
}

int Graf::get_noduri()
{
	return this->noduri;
}

int Graf::get_muchii()
{
	return this->muchii;
}

int Graf::get_vizitat(int nod)
{
	return vizitat[nod];
}

void Graf::adauga_muchie_neorientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini[nod2].push_back(nod1);
}

void Graf::adauga_muchie_orientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
}

void Graf::sorteaza()
{
	for (int i = 1; i <= noduri; i++)
		vecini[i].sort();
}

void Graf::dfs(int nod)
{
	//cout << nod << " ";
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			dfs(*i);
}

void Graf::componente_conexe()
{
	int sol = 0;
	int N = this->get_noduri();
	this->sorteaza();

	for (int i = 1; i <= N; i++)
		if (this->get_vizitat(i) != 1)
		{
			sol += 1;
			this->dfs(i);
		}

	cout << sol;
}

void Graf::bfs(int nod)
{
	int start = nod;
	queue<int>coada;
	vizitat[nod] = 1;
	coada.push(nod);
	unordered_map<int, int>distanta;

	for (int i = 1; i <= noduri; i++)
		distanta[i] = 0;

	while (coada.size())
	{
		nod = coada.front();
		//cout << nod << " ";
		coada.pop();
		for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
			if (!vizitat[*i])
			{
				vizitat[*i] = 1;
				coada.push(*i);
				distanta[*i] = distanta[nod] + 1;
			}
	}
	for (int i = 1; i <= noduri; i++)
		if (i != start && distanta[i] == 0)
			o << "-1" << " ";
		else
			o << distanta[i] << " ";
}

void Graf::tool_sortare_topologica(int nod)
{
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			tool_sortare_topologica(*i);

	stiva_sortare_topologica.push(nod);
}

void Graf::sortare_topologica()
{
	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
			tool_sortare_topologica(i);

	while (stiva_sortare_topologica.size())
	{
		o << stiva_sortare_topologica.top() << " ";
		stiva_sortare_topologica.pop();
	}
}

int main()
{
	int N, M;

	f >> N >> M;

	Graf g(N, M);

	for (int i = 1; i <= M; i++)
	{
		int st, dr;
		f >> st >> dr;
		g.adauga_muchie_orientat(st, dr);
	}

	
	g.sortare_topologica();

	return 0;
}