Pagini recente » Cod sursa (job #141278) | Cod sursa (job #1608023) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #715501) | Cod sursa (job #3225378)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
size_t N;
size_t M;
size_t source;
vector<vector<size_t>> adj;
vector<int> in_rank;
public:
explicit Solutuion(ifstream &in) {
in >> N >> M;
adj.resize(N + 1);
in_rank.resize(N + 1, 0);
size_t node1, node2;
for (size_t i = 1; i <= M; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
++in_rank[node2];
}
}
vector<int> solve() {
vector<int> topsort;
topsort.reserve(N);
vector<bool> sorted(N + 1, false);
queue<int> q;
for (int source = 1; source < N + 1; source++)
if (in_rank[source] == 0)
q.push(source);
while (!q.empty()) {
int curr_node = q.front();
q.pop();
topsort.push_back(curr_node);
for (auto neigh : adj[curr_node]) {
if (--in_rank[neigh] == 0) {
q.push(neigh);
}
}
}
return topsort;
}
};
int main() {
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> solution = Solutuion(in).solve();
copy(solution.begin(), solution.end(), ostream_iterator<int>(out, " "));
in.close();
out.close();
return 0;
}