Pagini recente » Cod sursa (job #1124418) | Cod sursa (job #1118090) | Cod sursa (job #1128250) | Cod sursa (job #1239898) | Cod sursa (job #1134222)
// Compilare g++ sursa.cpp -o binar
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMax 50100
//Complexity = O(N+M)
int M, N, R[NMax], deg[NMax], L[NMax]; vector<int> G[NMax];
void sortare (void) {
int i, j, k, sizeL, sizeR;
sizeL=0;
sizeR=0;
for (i=1; i<=N; ++i)
{
if (deg[i]==0) {
sizeL++;
L[sizeL]=i;
}
}
for (i=1; i<=sizeL; ++i)
{
for (j=0; j<G[L[i]].size(); ++j)
{
deg[G[L[i]][j]]--;
if (deg[G[L[i]][j]]==0) {
//put node G[L[i]][j] into list L and increment sizeL
sizeL++;
L[sizeL] = G[L[i]][j];
}
}
sizeR++;
R[sizeR]= L[i];
}
for (i=1; i<=N; ++i)
{
printf("%d ",R[i]);
}
}
int main (void) {
int i,a,b;
freopen("sortaret.in", "rt", stdin);
freopen("sortaret.out", "wt", stdout);
//N - nr of nodes
//M - nr of connections (edges)
scanf("%d %d\n", &N, &M);
for(i = 1; i <= M; i++)
scanf("%d %d", &a, &b), G[a].push_back(b), deg[b]++;
sortare();
return 0;
}