Cod sursa(job #1112103)

Utilizator varga13VarGaz13 varga13 Data 19 februarie 2014 13:51:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#define mx 50008
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int m,n, Grad[mx]; // Gradul Intern (cate intra)
bool viz[mx];
vector<int> Ad[mx], Sol;

void Read()
{
    f>>n>>m;
    int a,b;
    for(int i =0;i<m;++i)
    {
        f>>a>>b;
        Ad[a].push_back(b);
        Grad[b]++;
    }
}

void Write()
{
    for(int i=0;i<Sol.size();++i)
        g<<Sol[i]<<' ';
}

void Dfs(int s)
{
    for(int i=0;i<Ad[s].size();++i)
    {
        Grad[Ad[s][i]]--;
        viz[Ad[s][i]]=1;
        if(Grad[Ad[s][i]]==0)
        {
            Sol.push_back(Ad[s][i]);
            Dfs(Ad[s][i]);
        }



    }
}


int main()
{
    Read();
    for(int i=1;i<=n;++i)
        if((Grad[i]==0)&&(!viz[i]))
        {
            viz[i]=1;
            Sol.push_back(i);
            Dfs(i);
        }
    Write();
    g.close();
    f.close();
    return 0;
}