Cod sursa(job #2052832)

Utilizator HaripAlexHarip Alexandru HaripAlex Data 31 octombrie 2017 08:34:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 50010
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> G[NMAX];

int n,m,d[NMAX],lg[NMAX],viz[NMAX],lgm,x,y;
void DFS(int x);
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        {
            fin>>x>>y;
            G[x].push_back(y);
            d[y]++;
        }
    for(int i=1;i<=n;i++)
        if(d[i]==0)
           DFS(i);
    for(int i=0;i<=lgm;i++)
        for(int j=1;j<=n;j++)
         if(lg[j]==i)
           fout<<j<<' ';
}
void DFS(int x)
{
    int c[NMAX]={0},p,u;
    viz[x]=1;
    p=u=1;
    c[1]=x;
    while(p<=u)
    {
        x=c[p++];
        for(int i=0;i<G[x].size();i++)
        {
            y=G[x][i];
            if(viz[y]==0)
            {
                c[++u]=y;
                viz[y]=1;
                lg[y]=lg[x]+1;
                if(lg[y]>lgm)
                    lgm=lg[y];
            }
        }
    }
}