Pagini recente » Cod sursa (job #2200265) | Cod sursa (job #2835342) | Cod sursa (job #838732) | Cod sursa (job #2439459) | Cod sursa (job #2756826)
#include<cstdio>
#include<vector>
using namespace std;
const int N = 50002;
int n, m, grad[N], x[N];
vector <int> v[N];
// pun pe 1 cand devine un nod cu grad intern 0
bool marcat[N];
void citire() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
// citesc muchia orientata xy
int x, y;
scanf("%d%d", &x, &y);
// lista de adiacenta, nodului x ii adaug toti vecinii
v[x].push_back(y);
// grad[y] va retine cate muchii intra
++grad[y];
}
}
void rez() {
int p = 0, q = -1;
// adaug in coada x toate nodurile care au gradul intern 0
for (int i = 1; i <= n; ++i)
if (grad[i] == 0) {
x[++q] = i;
marcat[i] = true;
}
// cat timp coada nu e goala
while (p <= q) {
// trecem prin toti vecinii nodului
for (int i = 0; i < (int) v[x[p]].size(); ++i) {
// daca nu ajung la 0
if (!marcat[v[x[p]][i]])
// trec prin toti vecinii si scad cu 1 gradul sau de intrare
--grad[v[x[p]][i]];
// daca am ajuns la 0, il adaug in coada ca sa ii scad si vecinii lui
if (grad[v[x[p]][i]] == 0 && !marcat[v[x[p]][i]]) {
marcat[v[x[p]][i]] = true;
x[++q] = v[x[p]][i];
}
}
++p;
}
for (int i = 0; i < p; ++i)
printf("%d ", x[i]);
printf("\n");
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
citire();
rez();
return 0;
}