Cod sursa(job #2427427)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 31 mai 2019 20:16:53
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, x, y, nr, pas;
int sterse[50005];
set <int> nesterse;
vector <int> v[50005];
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        nesterse.insert(i);
    while(!nesterse.empty())
    {
        set <int>::iterator it;
        queue <int> ptsters;
        for(it=nesterse.begin();it!=nesterse.end();it++)
        {
            int sz=v[*it].size();
            nr=0;
            for(int i=0;i<sz&&!nr;i++)
                if(sterse[v[*it][i]]==0)
                    nr=1;
            if(!nr)
            {
                printf("%d ",(*it));
                ptsters.push(*it);
            }
        }
        while(!ptsters.empty())
        {
            nesterse.erase(nesterse.find(ptsters.front()));
            sterse[ptsters.front()]=1;
            ptsters.pop();
        }
    }
    return 0;
}