Pagini recente » Cod sursa (job #2004171) | Cod sursa (job #3244744) | Cod sursa (job #1624518) | Cod sursa (job #2468545) | Cod sursa (job #2425109)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
unordered_set<int> unmarked;
class Graph
{
private:
int n, m;
vector<vector<int>>edges;
public:
Graph(int _n, int _m) : n{_n}, m{_m}{
edges.resize(_n + 1, vector<int>());
}
void addEdge(int x, int y){
edges[x].push_back(y);
}
vector<int> getTopologicSort(int startNode)
{
queue<int> q;
vector<int> answ;
q.push(startNode);
while (!q.empty())
{
int k = q.front(); q.pop();
unmarked.erase(unmarked.find(k));
answ.push_back(k);
for (int &x : edges[k])
q.push(x);
}
return answ;
}
};
int main()
{
int n, m, x, y, startNode;
fin >> n >> m;
Graph g(n, m);
fin >> x >> y;
g.addEdge(x, y);
startNode = x;
for (int i = 2; i <= m; ++i)
{
fin >> x >> y;
g.addEdge(x, y);
}
for(int i = n; i >= 1; i--)
unmarked.emplace(i);
while (unmarked.size())
{
vector<int> answ = g.getTopologicSort(startNode);
for_each(answ.begin(), answ.end(), [](int &c) {fout << c << " ";});
}
return 0;
}