Cod sursa(job #1124724)

Utilizator costyv87Vlad Costin costyv87 Data 26 februarie 2014 13:30:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 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[y].push_back(x);
        }
}

void dfs(int x)
{
    int i;

    bf[x]=true;

    for (i=0;i<a[x].size();i++)
        if (bf[a[x][i]]==false)
            dfs(a[x][i]);
    sol.push_back(x);
}

void solve()
{
    int i;
    for (i=1;i<=n;i++)
        if (bf[i]==false)
            dfs(i);
}

void write()
{
    int i;

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

}

int main() {

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

}