Cod sursa(job #3261637)

Utilizator Shaan_StefanShaan Stefan Shaan_Stefan Data 7 decembrie 2024 09:33:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <vector>
#include <queue>

#define NMAX 50000

using namespace std;

FILE *in=fopen("sortaret.in", "r"), *out=fopen("sortaret.out", "w");

vector<int> ade[NMAX+2];
int adi[NMAX+2], n, m, x, y, f[NMAX+2];
queue<int> nods;
void sortTop()
{
    while(!nods.empty())
    {
        int tp=nods.front();
        fprintf(out, "%d ", tp);
        nods.pop();
        for(int i=0; i<ade[tp].size(); i++)
        {
            adi[ade[tp][i]]--;
            if(adi[ade[tp][i]]==0)
                nods.push(ade[tp][i]);
        }
    }
}

bool findArc(int x, int y)
{
    for(int i=0; i<ade[x].size(); i++)
        if(ade[x][i]==y)
            return 1;
    return 0;
}

int main()
{

    fscanf(in, "%d %d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        fscanf(in, "%d %d", &x, &y);
        if(!findArc(x, y))
        {
            ade[x].push_back(y);
            adi[y]++;
            f[y]=1;
        }
    }

    for(int i=1; i<=n; i++)
        if(f[i]==0)
            nods.push(i);

    sortTop();

    return 0;
}