Pagini recente » Cod sursa (job #2736104) | Cod sursa (job #428044) | Cod sursa (job #3258930) | Rating Divia Negoescu (divianegoescu) | Cod sursa (job #811861)
Cod sursa(job #811861)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 50005;
vector <int> G[MAX_N];
int N, M;
int InGr[MAX_N];
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
void read() {
fin >> N >> M;
for (int i = 0; i < M; ++i) {
int a, b;
fin >> a >> b;
G[a].push_back(b);
++InGr[b];
}
}
void solve() {
queue <int> Q;
// Push the nodes that have no edge going to them
for (int i = 1; i <= N; i++) {
if (InGr[i] == 0) {
Q.push(i);
}
}
while (!Q.empty()) {
int current = Q.front();
Q.pop();
fout << current << " ";
for (vector<int>::iterator it = G[current].begin(); it != G[current].end(); ++it) {
--InGr[*it];
if (InGr[*it] == 0) {
Q.push(*it);
}
}
}
fout << "\n";
}
int main() {
read();
solve();
return 0;
}