Cod sursa(job #2468059)

Utilizator RedXtreme45Catalin RedXtreme45 Data 5 octombrie 2019 12:27:28
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
vector <int> v[50001];
vector <int>:: iterator it;
struct {
    int in;
    int ex;
}s[50001];
int c[50001];
int p=1,u=0;
void sortare()
{
    while (p<=u)
    {
        for (it=v[c[p]].begin();it!=v[c[p]].end();++it)
        {
            s[*it].in--;
            if (s[*it].in==0)
            {
                u++;
                c[u]=*it;
            }
        }
        p++;
    }
}
int main()
{
    int i,a,b;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        s[a].ex++;
        s[b].in++;
    }
    for (i=1;i<=n;i++)
    {
        if (s[i].in==0)
        {
            u++;
            c[u]=i;
        }
    }
    sortare();
    for (i=1;i<=u;i++)
        fout<<c[i]<<" ";
    return 0;
}