Cod sursa(job #2804598)

Utilizator mirunavrAvram Miruna-Alexandra mirunavr Data 21 noiembrie 2021 11:51:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb

#include<bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int> v[200001];

int n,m,x,y;
int intern_grade[200001];
queue<int> q;
vector<int> topo_sort;

void add(int node1,int node2){
    v[node1].push_back(node2);
}

void topo(){
    for(int i=1;i<=n;i++)
        if(intern_grade[i]==0)
            q.push(i);
    while(q.size()!=0){
        int node=q.front();
        q.pop();
        topo_sort.push_back(node);
        for(int i=0;i<v[node].size();i++)
        {
            intern_grade[v[node][i]]=intern_grade[v[node][i]]-1;
            if(intern_grade[v[node][i]]==0)
                q.push(v[node][i]);
        }
    }
}

int main() {

    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>x>>y;
        intern_grade[y]+=1;
        add(x,y);
    }
    topo();
    for(int i=0;i<topo_sort.size();i++)
        g<<topo_sort[i]<<" ";

}