Pagini recente » Cod sursa (job #915581) | Cod sursa (job #558446) | Cod sursa (job #2318623) | Cod sursa (job #350584) | Cod sursa (job #2969903)
/*
* https://www.infoarena.ro/problema/sortaret 100p
* O(V+E)
*/
#include <bits/stdc++.h>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int V, E;
vector<vector<int>> adjList;
vector<int> inDegree;
void init(){
adjList.resize(V+1);
inDegree.resize(V+1);
}
void read(){
in >> V >> E;
init();
for(int i = 0; i < E; i++){
int u, v;
in >> u >> v;
adjList[u].push_back(v);
inDegree[v]++;
}
}
void topologicalSorting(){
queue<int> q;
for(int i = 1; i <= V; i++)
if(!inDegree[i])
q.push(i);
while(!q.empty()){
int u = q.front();
q.pop();
out << u << ' ';
for(auto v: adjList[u]){
inDegree[v]--;
if(!inDegree[v])
q.push(v);
}
}
}
int main() {
read();
topologicalSorting();
return 0;
}