Cod sursa(job #2673638)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 17 noiembrie 2020 13:27:38
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
using namespace std;
deque <int> S;
deque <int> Li[50010];
vector <int> sol;
bitset <50010> a[50010];
int nr[50010],i,n,m,x,y;
void kahn(){
    while (!S.empty()){
        int n=S.front();
        sol.push_back(n);
        S.pop_front();
        for (int i=0;!Li[n].empty();){
            int m=Li[n][i];
            Li[n].pop_front();
            nr[m]--;
            if (nr[m]==0){
                S.push_back(m);
            }
        }
    }
}
int main () {
    ifstream fin ("sortaret.in");
    ofstream fout ("sortaret.out");
    fin>>n>>m;
    while (fin>>x>>y){
        if (a[x][y]==0){
            ///Lf[y].push_back(x);
            nr[y]++;
            Li[x].push_back(y);
            a[x][y]=1;
        }
    }
    for (i=1;i<=n;i++){
        if (nr[i]==0){
            S.push_back(i);
        }
    }
    kahn();
    for (i=0;i<sol.size();i++){
        fout<<sol[i]<<" ";
    }
    return 0;
}