Cod sursa(job #875673)

Utilizator ericptsStavarache Petru Eric ericpts Data 10 februarie 2013 17:13:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>
#define maxn 50005
using namespace std;

vector<int> graf[maxn];

int n;
int deg[maxn];
int q[maxn];
void read()
{
    freopen("sortaret.in","r",stdin);

    int m,a,b;
    scanf("%d %d\n",&n,&m);

    while(m--)
    {
        scanf("%d %d\n",&a,&b);
        deg[b]++;
        graf[a].push_back(b);
    }

}

void solve()
{
    vector<int> :: iterator it;
    int i,x;
    for(i=1;i<=n;++i)
        if(deg[i]==0)
            q[++q[0]]=i;

    for(i=1;i<=n;++i)
    {
        x = q[i];
        for(it=graf[x].begin();it != graf[x].end(); ++ it)
        {
            deg[*it]--;
            if(deg[*it]==0)
                q[++q[0]]=*it;
        }
    }
}

void write()
{
    int i;
    freopen("sortaret.out","w",stdout);
    for(i = 1; i <= n ; ++ i)
        printf("%d ",q[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}