Pagini recente » Cod sursa (job #47593) | Cod sursa (job #725540) | Diferente pentru problema/seti intre reviziile 6 si 2 | Monitorul de evaluare | Cod sursa (job #3333756)
#include <fstream>
#include <vector>
#include <queue>
std::ifstream fin("topsort.in");
std::ofstream fout("topsort.out");
class Graph{
private:
int V;
std::vector<std::vector<int>>adj;
std::vector<int>in_degree;
public:
Graph(int v) {
V = v;
adj.resize(V+1);
}
void addEdges(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(auto& vecin : adj[c]) {
in_degree[vecin]--;
if(!in_degree[vecin]) {
pq.push(vecin);
}
}
}
}
};
int main(void) {
int m, n;
fin >> n>> m;
Graph g(n);
int x1, x2;
for(int i=0;i<m;++i) {
fin >> x1 >> x2;
g.addEdges(x1, x2);
}
g.kahn();
return 0;
}