Cod sursa(job #1452545)

Utilizator refugiatBoni Daniel Stefan refugiat Data 21 iunie 2015 12:22:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<iostream>
#include<fstream>
#include<stack>
#include<bitset>
#include<list>
using namespace std;
list<int> g[50002];
stack<int> s;
bitset<50002> b;
void util(int x)
{
    b[x]=1;
    list<int>::iterator i;
    for(i=g[x].begin();i!=g[x].end();++i)
    {
        if(b[*i]==0)
        {
            util(*i);
        }
    }
    s.push(x);
}
void topol(int n)
{
    int i;
    for(i=1;i<n;++i)
    {
        if(b[i]==0)
        {
            util(i);
        }
    }
}
int main()
{
    //ifstream si;
    //si.open("gardul.in");
    FILE* si=fopen("sortaret.in","r");
    //FILE* so=fopen("ordine.out","w");
    ofstream so;
    so.open("sortaret.out");
    int n,m;
    fscanf(si,"%i %i",&n,&m);
    int a,b;
    int i;
    for(i=0;i<m;++i)
    {
        fscanf(si,"%i %i",&a,&b);
        g[a].push_back(b);
    }
    ++n;
    topol(n);

    /*list<int>::iterator x;
    for(i=1;i<n;++i)
        for(x=g[i].begin();x!=g[i].end();++x)
        {
            cout<<i<<' '<<*x<<'\n';
        }*/
    while(s.size())
    {
        so<<s.top()<<' ';
        s.pop();
    }
    so<<'\n';
}