Pagini recente » Cod sursa (job #1238725) | Cod sursa (job #2296685) | Cod sursa (job #956957) | Cod sursa (job #2255845) | Cod sursa (job #2222366)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <queue>
using namespace std;
int main() {
int N, M;
int first, second;
vector<vector<int>> graph;
ifstream input("sortaret.in");
ofstream output("sortaret.out");
input >> N >> M;
for (int i = 0; i < N; i++) {
vector<int> v;
graph.push_back(v);
}
for (int i = 0; i < M; i++) {
input >> first >> second;
graph[first - 1].push_back(second - 1);
}
vector<int> inDegree(N, 0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < graph[i].size(); j++) {
inDegree[graph[i][j]]++;
}
}
queue<int> q;
vector<int> topSort;
for (int i = 0; i < inDegree.size(); i++)
if (inDegree[i] == 0)
q.push(i);
int cnt = 0;
while (!q.empty()) {
int element = q.front();
q.pop();
topSort.push_back(element);
for (int i = 0; i < graph[element].size(); i++) {
inDegree[graph[element][i]]--;
if (inDegree[graph[element][i]] == 0)
q.push(graph[element][i]);
}
cnt++;
}
if (cnt != N) {
output << "-1";
} else {
for (int i = 0; i < topSort.size(); i++)
output << topSort[i] + 1 << " ";
}
input.close();
output.close();
return 0;
}