Cod sursa(job #2089396)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 16 decembrie 2017 14:30:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 500001

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector < int > G[NMAX];
int di[NMAX],n,m,x,y,p,u,c[NMAX],z,w;

int main()
{

   int u=0;
    fin>>n>>m;
    for( int i = 1; i <= m ; i ++)
    {
        fin>>x>>y;
        di[y]++;
        G[x].push_back(y);
    }
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!di[i])
        {
          u++;
          c[u]=i;
        }
    }
    int p=1;
    while(p<=u)
    {
        z=c[p];
        p++;
        fout<<z<<" ";
        for(int i = 0 ; i < G[z].size();i++)
        {
            w=G[z][i];
            di[w]--;
            if(!di[w])
            {
                u++;
                c[u]=w;
            }

        }

    }
    return 0;
}