Cod sursa(job #3150462)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 16 septembrie 2023 20:26:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include<vector>
using namespace std;

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

int n, m, index[50001];
vector<int> a[50001], bucket[100001];
bool notStart[50001];

//bool tk[50001]; (no cycles)
void df(int x, int ind=0)
{
    index[x]=max(index[x], ind);
    for(int i=0;i<a[x].size();i++)
        df(a[x][i], ind+1);
}

int main() {

    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y;
        in>>x>>y;
        notStart[y]=true;
        a[x].push_back(y);
    }


    for(int i=1;i<=n;i++)
        if(!notStart[i])
            df(i);

    for(int i=1;i<=n;i++)
        bucket[index[i]].push_back(i);

    for(int i=0;i<=m;i++)
        for(int j=0;j<bucket[i].size();j++)
            out<<bucket[i][j]<<' ';


    return 0;
}