Pagini recente » Cod sursa (job #1190504) | Cod sursa (job #1705151) | Cod sursa (job #2220451) | Cod sursa (job #778710) | Cod sursa (job #676874)
Cod sursa(job #676874)
// Sotare topologica - Infoarena Arhiva Educationala
// Dumitran Marius Feb 2012
// O(n+m)
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define maxn 50001
vector <int> vec[maxn];
vector <int> solutie;
int nr[ maxn ];
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
for( int i = 1; i <= m; ++i) {
int a, b;
scanf("%d %d", &a, &b);
nr[b]++;
vec[a].push_back(b);
}
for( int i = 1; i <= n; ++i) {
if(nr[i] == 0)
solutie.push_back(i);
}
for( int i = 0; i < solutie.size(); ++i) {
int new_nod = solutie[i];
printf("%d ", new_nod);
for( int j = 0; j < vec[ new_nod ].size(); ++j) {
nr[ vec[ new_nod ][j]]--;
if( nr[ vec[ new_nod][j]] == 0) {
solutie.push_back(vec[new_nod][j]);
}
}
}
printf("\n");
return 0;
}