Cod sursa(job #1799580)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 6 noiembrie 2016 15:12:26
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
int i,j,x,k,m,n,y,h,d[50001],l;
vector<int>a[50001];
bool w[50001],viz[50001];
vector<int>v;
int main()
{
    ifstream f("sortaret.in");
    f>>n>>m;
    for(i=1;i<=n;++i){viz[i]=0;w[i]=0;}
    for(i=0;i<m;++i)
    {
        f>>x>>y;
        if(!w[y])
        {
            a[x].push_back(y);
            w[y]=1;
        }
    }
    f.close();
    for(i=1;i<=n;++i)d[i]=a[i].size();
    ofstream g("sortaret.out");
    for(l=1;l<=n;++l)
    {
        if(w[l]<1)
        {
            v.push_back(l);
            h=1;
            while(h)
            {
                x=v[h-1];
                g<<x<<" ";
                viz[x]=1;
                --h;v.pop_back();
                for(i=d[x]-1;i>-1;--i)
                {
                    y=a[x][i];
                    if(!viz[y])
                    {
                        //viz[y]=1;
                        v.push_back(y);
                        ++h;
                    }
                }
            }
        }
    }
    g.close();
    return 0;
}