Pagini recente » Cod sursa (job #298990) | Cod sursa (job #2230142) | Cod sursa (job #1697542) | Cod sursa (job #99932) | Cod sursa (job #2692583)
#include<fstream>
#include<list>
#include<cstring>
#include<string.h>
#include<stack>
using namespace std;
ifstream cin("sortare.in");
ofstream cout("sortare.out");
class graph
{
private:
int n;
list<int>* adj;
void DFS(int n, bool* viz,stack<int> &s);
public:
graph(int n);
void addEdge(int x, int y);
void printsorted();
~graph();
};
graph::graph(int n)
{
this->n = n;
adj = new list<int>[n+1];
}
graph::~graph()
{
delete[] adj;
}
void graph::addEdge(int x, int y)
{
adj[x].push_back(y);
}
void graph::DFS(int n, bool* viz, stack<int>& s)
{
viz[n] = true;
for (auto it : adj[n])
DFS(it, viz, s);
s.push(n);
}
void graph::printsorted()
{
stack<int> s;
bool* viz = new bool[n + 1];
memset(viz, false, n + 1);
for (int i = 1; i <= n; i++)
if (!viz[i])
DFS(i, viz, s);
while (!s.empty())
{
cout << s.top()<<" ";
s.pop();
}
}
int main()
{
int n, m, x, y;
cin >> n >> m;
graph G(n);
for (int i = 1; i <= m; i++)
{
cin >> x >> y;
G.addEdge(x, y);
}
G.printsorted();
cin.close();
cout.close();
return 0;
}