Pagini recente » Cod sursa (job #1510945) | Statistici Ghergu Ioana (iioaaana777) | Statistici Andreea Gabriela (gabriela95) | Cod sursa (job #117084) | Cod sursa (job #3275931)
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define maxSize 100001
using namespace std;
vector<vector<int>> readAdjacencyList(ifstream &fin, int nodes, int edges, bool isDirected = false) {
vector<vector<int>> adjList(nodes + 1);
for (int i = 0; i < edges; i++) {
int x, y;
fin >> x >> y;
adjList[x].push_back(y);
if (!isDirected) {
adjList[y].push_back(x);
}
}
return adjList;
}
vector<int> kahnsTopologicalSort(const vector<vector<int>>& adjList) {
vector<int> inDegree(adjList.size(), 0);
vector<int> topOrd;
queue<int> q;
for (int i = 1; i < adjList.size(); i++) {
for (auto elem : adjList[i]) {
inDegree[elem]++;
}
}
for (int i = 1; i < inDegree.size(); i++) {
if(inDegree[i] == 0) {
q.push(i);
}
}
while(!q.empty()) {
int node = q.front();
topOrd.push_back(node);
q.pop();
for(auto adjNode : adjList[node]) {
inDegree[adjNode]--;
if(inDegree[adjNode] == 0) {
q.push(adjNode);
}
}
}
if (topOrd.size() != adjList.size() - 1) {
return vector<int>();
}
return topOrd;
}
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int nodes, edges;
fin >> nodes >> edges;
auto adjList = readAdjacencyList(fin, nodes, edges, true);
auto topSort = kahnsTopologicalSort(adjList);
for (auto elem : topSort) {
fout << elem << " ";
}
fout << endl;
fin.close();
fout.close();
return 0;
}