Nu aveti permisiuni pentru a descarca fisierul grader_test1.in
Cod sursa(job #2424189)
Utilizator | Data | 22 mai 2019 19:10:24 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.04 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector< vector<int> >v;
vector<int> sol;
queue <int> q;
int main() {
int n, m;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
cin >> n >> m;
v.resize(n + 1);
int outdeg[n + 1];
for (int i = 0; i <= n; i++) {
outdeg[i] = 0;
}
bool seen[n + 1];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
v[b].push_back(a);
outdeg[a]++;
}
for (int i = 1; i <= n; i++) {
seen[i] = false;
if (outdeg[i] == 0) {
q.push(i);
}
}
while(!q.empty()) {
// cout << "k = ";
int k = q.front();
sol.push_back(k);
q.pop();
for (int i = 0; i < v[k].size(); i++) {
outdeg[v[k][i]] --;
if (outdeg[v[k][i]] == 0) {
q.push(v[k][i]);
}
}
}
for (int i = sol.size() - 1; i >= 0; i--) {
cout << sol[i] << " ";
}
return 0;
}