Cod sursa(job #2052171)

Utilizator pibogaBogdan piboga Data 30 octombrie 2017 10:08:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#define mxvf 50002

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");

vector <int> lst[mxvf];
vector <int> af;
vector <int>::iterator it;

bool viz[mxvf],unic;
int nvf,nmc,i,x,y,need,sz;

void srt(int nod)
{
    vector <int>::iterator itt;
    viz[nod]=1;
    for (itt=lst[nod].begin(); itt!=lst[nod].end(); ++itt)
    {
        int need=*itt;
        if (!viz[need])
        {
            srt(need);
        }
    }

    af.push_back(nod);
}

int main()
{
    fin >> nvf >> nmc;
    for (i=1;i<=nmc;++i)
    {
        fin >> x >> y;
        unic=1;
        for (it=lst[x].begin();it!=lst[x].end();++it)
        {
            need=*it;
            if (need==y)
            {
                unic=0;
                break;
            }
        }
        if (unic)
        {
            lst[x].push_back(y);
        }
    }

    for (i=1;i<=nmc;++i)
    {
        if (!viz[i])
        {
            srt(i);
        }
    }

    sz=af.size()-1;
    for (i=sz;i>=0;--i)
    {
        fout << af[i] << ' ';
    }

    return 0;
}