Pagini recente » Cod sursa (job #475784) | Cod sursa (job #578449) | Cod sursa (job #3138860) | Cod sursa (job #2821195) | Cod sursa (job #2905293)
#include <bits/stdc++.h>
using namespace std;
const int dim = 50005;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
class Graph
{
private:
int node_count, edge_count;
vector <int> adj[dim];
public:
Graph ()
{
node_count = 0;
edge_count = 0;
}
Graph (int nodes, int edges)
{
node_count = nodes;
edge_count = edges;
}
void Make_Graph (int nodes, int edges)
{
node_count = nodes;
edge_count = edges;
}
void Add_edge (int node1, int node2)
{
adj[node1].push_back(node2);
}
int NrNoduri ()
{
return node_count;
}
void Afis_Graph ()
{
for (int i = 1; i <= node_count; i++, cout << "\n")
{
cout << i << ": ";
for (int j : adj[i])
cout << j << " ";
}
}
void DFS_SortTop (int node, vector <int> &viz, stack <int> &st)
{
viz[node] = 1;
for (int i : adj[node])
if (!viz[i])
DFS_SortTop(i, viz, st);
st.push(node);
}
stack <int> SortTop (vector <int> &viz, stack <int> &st)
{
for (int i = 1; i <= node_count; i++)
if (!viz[i])
{
DFS_SortTop(i, viz, st);
}
return st;
}
};
vector <int> viz(dim);
stack <int> st;
Graph G;
int main()
{
int n , m;
fin >> n >> m;
G.Make_Graph(n , m);
for (int i = 1; i<= m; i++)
{
int x, y;
fin >> x >> y;
G.Add_edge(x, y);
}
stack <int> sol = G.SortTop(viz, st);
while (!sol.empty())
{
fout << sol.top() << " ";
sol.pop();
}
return 0;
}