Pagini recente » Cod sursa (job #1575049) | Cod sursa (job #2863956) | Cod sursa (job #2109868) | Cod sursa (job #512966) | Cod sursa (job #2432674)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <iterator>
#define NMAX 50000
using namespace std;
ofstream fout("sortaret.out");
ifstream fin("sortaret.in");
class Graph {
public:
vector<int> adjList[NMAX];
vector<bool> visited;
vector<int> tdesc;
vector<int> order;
int contor = 0;
int nodes;
Graph(int n) {
visited.resize(n + 1, 0);
tdesc.resize(n + 1, 0);
nodes = n;
}
~Graph() {
}
void addEdge(int x, int y) {
adjList[x].push_back(y);
}
void DFS(int nod) {
for (int i = 0; i < adjList[nod].size(); ++i) {
if (visited[adjList[nod][i]] == 0) {
visited[adjList[nod][i]] = 1;
++contor;
DFS(adjList[nod][i]);
}
}
tdesc[nod] = contor;
order.push_back(nod);
}
void Top_Sort() {
for (int i = 1; i <= nodes; ++i) {
if (visited[i] == 0) {
visited[i] = 1;
DFS(i);
}
}
for (int i = order.size() - 1; i >= 0; --i) {
fout << order[i] << " ";
}
}
};
int main() {
int n, m, x, y;
fin >> n >> m;
Graph graf(n);
for (int i = 0; i < m; ++i) {
fin >> x >> y;
graf.addEdge(x, y);
}
graf.Top_Sort();
return 0;
}