Cod sursa(job #150321)

Utilizator recviemAlexandru Pana recviem Data 6 martie 2008 20:47:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define fin  "sortaret.in"
#define fout "sortaret .out"
using namespace std;

    int m,n,d[100]; // d[i] = gradul interior al nodului i
    vector<int> graf[100];
    queue<int> _topSort;
    bool verif[100];

void citire()
{
    freopen(fin,"r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d %d ",&x,&y);
        graf[x].push_back(y);
        d[y]++;
    }
    fclose (stdin);
}

void topologic()
{
    bool bl=true;
    while (bl)
    {
        bl=false;
        for (int i=1;i<=n;i++)
            if (!verif[i] && d[i] == 0)
            {
                bl=true;
                verif[i]=1;
                for(vector<int>::iterator it=graf[i].begin(); it != graf[i].end(); it++)
                    d[*it]--;
                printf("%d ",i);
            }
    }
}


int main()
{
    citire();
    topologic();
    return 0;
}