Pagini recente » Cod sursa (job #940434) | Cod sursa (job #3326513) | Cod sursa (job #3310294) | Cod sursa (job #3344173) | Cod sursa (job #3333927)
#include <queue>
#include <fstream>
#include <vector>
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
class Graph{
private:
int V;
std::vector<std::vector<int>>adj;
std::vector<int>in_degree;
public:
Graph(int v) {
V = v+1;
adj.resize(V);
in_degree.resize(V);
}
void addEdge(int x, int y) {
adj[x].push_back(y);
in_degree[y]++;
}
void kahn() {
std::priority_queue<int>pq;
for(int i=1;i<=V;++i) {
if(!in_degree[i]) pq.push(i);
}
while(!pq.empty()) {
int c = pq.top();
fout << c << " ";
pq.pop();
for(int &vecin : adj[c]) {
in_degree[vecin]--;
if(!in_degree[vecin]) pq.push(vecin);
}
}
}
};
int main(void) {
int n, m, x, y;
fin >> n >> m;
Graph g(n);
for(int i=1;i<=m;++i) {
fin >> x >> y;
g.addEdge(x, y);
}
g.kahn();
return 0;
}