Pagini recente » Cod sursa (job #2065708) | Cod sursa (job #894908) | Cod sursa (job #3004297) | Cod sursa (job #947555) | Cod sursa (job #3252274)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream gout("sortaret.out");
int N_VERTEX;
int M_EDGES;
int in_degree[50000] = {0};
int position_counter[50001] = {0};
vector<int> edges[50001];
vector<int> sorted;
void read() {
int x;
int y;
fin >> N_VERTEX;
fin >> M_EDGES;
// Read all edges in adjacency list
for (int i = 0; i < M_EDGES; ++i) {
fin >> x >> y;
edges[x].push_back(y);
++in_degree[y];
}
}
void remove_vertex(int vertex) {
// Decrease incoming score of connected nodes
for (int outgoing = 0; outgoing < edges[vertex].size(); ++outgoing) {
--in_degree[edges[vertex][outgoing]];
}
// Empty vector of edges outgoing from vertex - not mandatory
edges[vertex].clear();
// Mark as visited
in_degree[vertex] = -1;
}
void topological_sort() {
int count_removed = 0;
while (count_removed < N_VERTEX) {
for (int i = 1; i <= N_VERTEX; ++i) {
if (in_degree[i] == 0) {
sorted.push_back(i);
remove_vertex(i);
++count_removed;
// bad implementation
}
}
}
}
void write() {
for (int i = 0; i < sorted.size(); ++i) {
gout << sorted[i] << " ";
}
gout << "\n";
}
int main() {
read();
topological_sort();
write();
fin.close();
gout.close();
return 0;
}