Pagini recente » Cod sursa (job #1063570) | Cod sursa (job #1886631) | Cod sursa (job #2983530) | Cod sursa (job #983475) | Cod sursa (job #2064951)
#include <fstream>
#include <set>
#include <vector>
std::ifstream cin("sortaret.in");
std::ofstream cout("sortaret.out");
class Graph {
public:
Graph(int n) {
incoming.resize(n);
outgoing.resize(n);
solution.reserve(n);
}
void addEdge(int from, int to) {
incoming[to].insert(from);
outgoing[from].insert(to);
}
void buildSolution() {
size_t idx;
for (idx = 0; idx < outgoing.size(); idx++) {
if (incoming[idx].empty()) {
solution.emplace_back(idx);
}
}
idx = 0;
while (idx < solution.size() &&
solution.size() < outgoing.size()) {
removeNode(solution[idx]);
idx++;
}
}
void printSolution() {
for (const auto& node : solution) {
cout << (node + 1) << " ";
}
}
private:
void removeNode(int node) {
for (const auto& to : outgoing[node]) {
incoming[to].erase(node);
if (incoming[to].empty()) {
solution.emplace_back(to);
}
}
outgoing[node].clear();
}
std::vector<std::set<int>> incoming;
std::vector<std::set<int>> outgoing;
std::vector<int> solution;
};
int main() {
int n, m, a, b;
cin >> n >> m;
Graph g(n);
while (m-- > 0) {
cin >> a >> b;
g.addEdge(a - 1, b - 1);
}
g.buildSolution();
g.printSolution();
return 0;
}