Pagini recente » Cod sursa (job #1836931) | Cod sursa (job #3190343) | Cod sursa (job #1846327) | Cod sursa (job #526329) | Cod sursa (job #3258907)
#include <fstream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.in");
void citire(int &noNodes, int &noEdges, vector<unordered_set<int>> &graph, vector<int> &inDegree) {
fin >> noNodes >> noEdges;
while(noEdges--) {
int firstNode, secondNode;
fin >> firstNode >> secondNode;
inDegree[secondNode]++;
graph[firstNode].insert(secondNode);
}
}
void sortare(int noNodes, vector<unordered_set<int>> &graph, vector<int> &inDegree, vector<int> &path) {
queue<int> Q;
for(int i=1; i<=noNodes; i++)
if(inDegree[i] == 0)
Q.push(i);
while(!Q.empty()) {
int currentNode = Q.front();
path.push_back(currentNode);
Q.pop();
for(auto neighbor : graph[currentNode]) {
inDegree[neighbor]--;
if(inDegree[neighbor] == 0)
Q.push(neighbor);
}
}
}
void afisare(vector<int> &path) {
for(auto element : path)
fout << element << ' ';
}
int main() {
int noNodes, noEdges;
vector<unordered_set<int>> graph(50005);
vector<int> inDegree(50005, 0);
vector<int> path;
citire(noNodes, noEdges, graph, inDegree);
sortare(noNodes, graph, inDegree, path);
afisare(path);
fin.close();
fout.close();
return 0;
}