Cod sursa(job #879070)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 14 februarie 2013 22:22:54
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> suc[101];
queue<int> q;
bool viz[101];
int sol[101],k,pred[101];
int n,m;
void sortop()
{
    while( !q.empty() )
    {
        int x=q.front() , number;
        for (int i=0 ; i<suc[x].size() ; ++i)
        {
            number=suc[x][i];
            -- pred[number];
            if(pred[number] == 0)
                q.push(number);
        }
        sol[++k]=x;
        q.pop();
    }
}
int main ()
{
    freopen("sortaret.in" , "r" , stdin);
    freopen("sortaret.out" , "w" , stdout);
    scanf("%d %d" , &n , &m);
    for (int i=1 ; i<=m ; ++i)
    {
        int x=0,y=0;
        scanf("%d %d" , &x , &y);
        ++ pred[y];
        suc[x].push_back(y);
    }
    for (int i=1 ; i<=n ; ++i)
        if(pred[i] == 0)
            q.push(i);
    sortop();
    for (int i=1 ; i<=k ; ++i)
        printf("%d " , sol[i]);
    return 0;
}