Pagini recente » Cod sursa (job #149910) | Cod sursa (job #240981) | Cod sursa (job #3142498) | Cod sursa (job #2493699) | Cod sursa (job #156480)
Cod sursa(job #156480)
// Sortare Topologica
// http://infoarena.ro/problema/sortaret
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 50005
int Deg[NMAX], Used[NMAX], n, m;
vector<int> Neighb[NMAX], Sol;
void depthFirst(int n) {
int i, sz = Neighb[n].size();
for (i = 0; i < sz; ++ i)
if (Used[Neighb[n][i]] == false) {
Used[Neighb[n][i]] = true;
depthFirst(Neighb[n][i]);
}
Sol.push_back(n);
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d", &n, &m);
int i, v1, v2;
for (i = 0; i < m; ++ i) {
scanf("%d %d", &v1, &v2);
Neighb[v1 - 1].push_back(v2 - 1);
-- Deg[v2 - 1];
}
for (i = 0; i < n; ++ i)
if (Deg[i] == 0) {
Used[i] = true;
depthFirst(i);
}
for (i = Sol.size() - 1; i >= 0; -- i)
printf("%d ", Sol[i] + 1);
return 0;
}