Pagini recente » Cod sursa (job #2020968) | Cod sursa (job #593820) | Cod sursa (job #1083071) | Cod sursa (job #1858044) | Cod sursa (job #2793653)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100001;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
/*
ifstream in("bfs.in");
ofstream out("bfs.out");
*/
/*
ifstream in("dfs.in");
ofstream out("dfs.out");
*/
/*
ifstream in("hakimi.in");
ofstream out("hakimi.out");
*/
class Graf
{
int NrNoduri;
vector<int> Adiacenta[MAX];
bool Vizitat[MAX] = {0};
stack<int> Stiva;
public:
Graf(int NrNoduri);
void AdaugaMuchie(int nod, int nodConectat);
void DfsT(int nod);
void Sortare_Topologica();
};
Graf::Graf(int NrNoduri)
{
this->NrNoduri = NrNoduri;
}
void Graf::AdaugaMuchie(int nod, int nodConectat)
{
Adiacenta[nod].push_back(nodConectat);
}
void Graf::DfsT(int nod)
{
Vizitat[nod] = 1;
for (auto i: Adiacenta[nod])
if (!Vizitat[i])
{
DfsT(i);
}
Stiva.push(nod);
}
void Graf::Sortare_Topologica ()
{
for(int i = 1; i <= NrNoduri; i++)
if(!Vizitat[i])
{
DfsT(i);
}
while (!Stiva.empty())
{
out << Stiva.top() << " ";
Stiva.pop();
}
}
int main()
{
int N, M;
in >> N >> M;
int nod1, nod2;
Graf g(N);
for(int i = 0; i < M; i++)
{
in >> nod1 >> nod2;
g.AdaugaMuchie(nod1, nod2);
}
g.Sortare_Topologica();
return 0;
}