Pagini recente » Cod sursa (job #1631432) | Cod sursa (job #2320046) | Cod sursa (job #2068497) | Cod sursa (job #740329) | Cod sursa (job #2334636)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
typedef unsigned int uint;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph
{
uint V;
vector<vector<uint>> adj;
void DFS(uint n, vector<bool> &v, stack<uint> &s);
public:
Graph(const uint V);
void Add_edge(uint x, uint y);
void TopologicalSort();
};
Graph::Graph(const uint V)
{
this->V = V;
adj.assign(V + 1, vector<uint>());
}
void Graph::Add_edge(uint x, uint y)
{
adj[x].emplace_back(y);
}
void Graph::DFS(uint n, vector<bool> &v, stack<uint> &s)
{
v[n] = true;
for (auto &i : adj[n])
if (!v[i])
DFS(i,v,s);
s.push(n);
}
void Graph::TopologicalSort()
{
vector<bool> v(V + 1, false);
stack<uint> sol;
for (uint i = 1; i <= V; ++i)
{
if (!v[i])
DFS(i,v,sol);
}
while (!sol.empty())
{
fout << sol.top() << ' ';
sol.pop();
}
}
int main()
{
uint n,m;
fin >> n >> m;
Graph G(n);
for (uint x,y,i = 0; i < m; ++i)
{
fin >> x >> y;
G.Add_edge(x,y);
}
G.TopologicalSort();
}