Pagini recente » Cod sursa (job #1668724) | Cod sursa (job #2648527) | Cod sursa (job #704220) | Cod sursa (job #146438) | Cod sursa (job #2606500)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
#define NMAX 100005
class Task {
std::vector<int> matrix[NMAX];
std::vector<bool> visited;
std::vector<int> intern_degree;
int N, M, S;
void read_input() {
std::ifstream in("sortaret.in");
in >> N;
in >> M;
intern_degree = std::vector<int>(N + 1, 0);
for (int i = 0; i < M; i++) {
int x;
int y;
in >> x;
in >> y;
// std::cout<<"y este"<<y<<"\n";
matrix[x].push_back(y);
intern_degree[y]++;
}
in.close();
}
void show_matrix() {
for (int i = 0; i < N; i++) {
std::cout<<i<<":";
for (int j = 0; j < matrix[i].size(); j++) {
std::cout<<matrix[i][j]<<" ";
}
std::cout<<"\n";
}
}
void show_degree() {
for (int i = 1; i <= N; i++) {
std::cout<<"degree["<<i<<"] = "<<intern_degree[i]<<"\n";
}
}
std::vector<int> topo() {
// show_degree();
std::vector<int> topological_order;
std::queue<int> zero_degree_nodes;
topological_order.push_back(0);
for (int i = 1; i <= N; i++) {
if (intern_degree[i] == 0) {
zero_degree_nodes.push(i);
}
}
while (!zero_degree_nodes.empty()) {
auto x = zero_degree_nodes.front();
zero_degree_nodes.pop();
topological_order.push_back(x);
for (auto const &elem : matrix[x]) {
intern_degree[elem]--;
if (intern_degree[elem] == 0) {
zero_degree_nodes.push(elem);
}
}
}
return topological_order;
}
void print(std::vector<int> topo) {
std::ofstream out("sortaret.out");
for (int i = 1; i <= N; i++) {
out<<topo[i]<<" ";
}
out<<"\n";
out.close();
return;
}
public:
void solve() {
read_input();
print(topo());
}
};
int main() {
Task* task = new Task();
task->solve();
delete(task);
return 0;
}