Pagini recente » Cod sursa (job #1552162) | Cod sursa (job #354766) | Cod sursa (job #1599748) | Cod sursa (job #2983531) | Cod sursa (job #2842225)
#include <bits/stdc++.h>
using namespace std;
/*/
For a given graph G, there must exist at least 1 node "v" that has its out-degree equal to 0.
Then, the topological sort for graph G will be equal to the topological sort for the graph G \ {v} + v /*/
template<class T>
vector<T>operator+(vector<T>v, T delta) {
for(auto &x : v)
x = x + delta;
return v;
}
template<class T>
ostream& operator << (ostream &cout, const vector<T>&v) {
for(auto x : v)
cout << x << ' ';
cout << '\n';
return cout;
}
class DirectedGraph {
vector<vector<int>>g;
vector<vector<int>>gt;
int N;
public:
DirectedGraph(int N = 0) : g(N), gt(N), N(N) {};
void add(int x, int y) {
assert(0 <= x && x < N);
assert(0 <= y && y < N);
g[x].push_back(y);
gt[y].push_back(x);
}
vector<int>topo_sort() {
queue<int>q;
vector<int>deg(N);
for(int i = 0; i < N; ++i)
deg[i] = gt[i].size();
for(int i = 0; i < N; ++i)
if(deg[i] == 0)
q.push(i);
vector<int>order;
while(!q.empty()) {
int nod = q.front();
q.pop();
order.push_back(nod);
for(int vec : g[nod]) {
deg[vec]--;
if(deg[vec] == 0) {
q.push(vec);
}
}
}
return order;
}
};
int main() {
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
int n, m;
cin >> n >> m;
DirectedGraph DG(n);
for(int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
DG.add(x - 1, y - 1);
}
vector<int>v = DG.topo_sort();
cout << (v + 1);
}