Cod sursa(job #1124734)

Utilizator costyv87Vlad Costin costyv87 Data 26 februarie 2014 13:34:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#define nmax 50010
using namespace std;
vector  <int> a[nmax];
vector <int> sol;
int gr[nmax];bool bf[nmax];
FILE *f,*g;
int n,m;

void read()
{
    int i,x,y;
    f=fopen("sortaret.in","r");
    g=fopen("sortaret.out","w");

    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++) {
        fscanf(f,"%d%d",&x,&y);
        gr[y]++;
        a[x].push_back(y);
        }
}

void df(int x)
{
    int i;
    bf[x]=true;

    sol.push_back(x);

    for (i=0;i<a[x].size();i++)
        if (bf[a[x][i]]==false)
            df(a[x][i]);


}

void solve()
{
    int i;
    for (i=1;i<=n;i++)
        if (gr[i]==0)
            df(i);

}

void write()
{
    int i;

    for (i=0;i<sol.size();i++)
        fprintf(g,"%d ",sol[i]);

    fclose(g);
}

int main() {

read();
solve();
write();

}