Pagini recente » Cod sursa (job #3225149) | Cod sursa (job #414413) | Cod sursa (job #1237742) | Cod sursa (job #1278388) | Cod sursa (job #999230)
Cod sursa(job #999230)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int MAXN = 50005;
int N, M, a, b;
int grad[MAXN];
vector <int> vecini[MAXN], coada;
void read() {
fin >> N >> M;
for (int i = 0; i < M; ++i) {
fin >> a >> b;
vecini[a].push_back(b);
++grad[b];//numarul de muchii care intra in nodul b
}
}
void solve() {
int i, node;
vector <int>::iterator it;
coada.push_back(0);
for (i = 1; i <= N; ++i)
if (grad[i] == 0)
coada.push_back(i);
i = 1;//la ce pozitie din coada suntem
while (coada.size() <= (unsigned)N) {//cand am toate nodurile in coada, ma opresc
node = coada[i++];
for (it = vecini[node].begin(); it != vecini[node].end(); ++it) {
--grad[*it];
if (grad[*it] == 0)//nod devenit izolat
coada.push_back(*it);
}
}
}
void write() {
for (int i = 1; i <= N; ++i)
fout << coada[i] << ' ';
fout << '\n';
}
int main() {
read();
solve();
write();
fin.close();
fout.close();
return 0;
}