Cod sursa(job #1850533)

Utilizator CriistinaMicula Cristina Criistina Data 18 ianuarie 2017 18:48:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 50002

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> gr[Nmax];
int p[Nmax];
int n, m, ok;

bool it_exists(int x, int y)
{
    for(auto i:gr[x])
    {
        if(i==y)
            return true;
    }
    return false;
}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        if(!it_exists(x, y)){
            gr[x].push_back(y);
            p[y]++;
        }
    }
    do
    {
        ok=0;
        for(int i=1;i<=n;i++)
        {
            if(p[i]==0)
            {
                p[i]=-1;
                ok=1;
                g<<i<<" ";
                for(unsigned int j=0;j<gr[i].size();j++)
                {
                    p[gr[i][j]]--;
                }
            }
        }
    }while(ok==1);
    return 0;
}