Cod sursa(job #1393167)

Utilizator AdrianGotcaAdrian Gotca AdrianGotca Data 19 martie 2015 09:54:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

FILE *f=fopen("sortaret.in","r");
FILE *g=fopen("sortaret.out","w");
int n,m;
vector <int> G[50500];
int c[50500];
int di[50500];
void read();
void solve();
void write();
int main()
{
    read();
    solve();
    write();
    return 0;
}

void read()
{
    int i=0,a=0,b=0;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
        fscanf(f,"%d%d",&a,&b),G[a].push_back(b),di[b]++;
}

void solve()
{
    int i=0,x=0;
    vector<int>::iterator it;
    for (i=1;i<=n;i++)
        if (di[i]==0) c[++c[0]]=i;
    for (i=1;i<=n;i++)
    {
        x=c[i];
        for (it=G[x].begin();it!=G[x].end();++it)
        {
            di[*it]--;
            if (di[*it]==0)
                c[++c[0]]=*it;
        }
    }
}

void write()
{
    for (int i=1;i<=n;i++)
        fprintf(g,"%d ",c[i]);
}