Cod sursa(job #3336453)

Utilizator anto_vscAntonia Voinescu anto_vsc Data 24 ianuarie 2026 18:56:57
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;


//DFS
//vector <int> L[100001];
//int viz[100001];
//
//
//
//void DFS(int x){
//
//    viz[x]=1;
//
//    for(auto vecin: L[x]){
//        if(!viz[vecin]){
//            viz[vecin]=1;
//            DFS(vecin);
//        }
//    }
//
//}
//
//
//int main(){
//    ifstream cin("dfs.in");
//    ofstream cout("dfs.out");
//
//    int n, m;
//    cin>>n>>m;
//
//    int comp=0;
//
//    for(int i=0; i<m; i++){
//        int x, y;
//        cin>>x>>y;
//        L[x].push_back(y);
//        L[y].push_back(x);
//    }
//
//    for(int i=1; i<=n; i++){
//        while(!viz[i]){
//            DFS(i);
//            comp++;
//        }
//    }
//
//    cout<<comp;
//
//    return 0;
//}

//BFS
//vector <int> L[100001];
//int viz[100001];
//queue <int> q;
//int dist[100001];
//
//
//void BFS(int x){
//
//    dist[x]=0;
//    viz[x]=1;
//    q.push(x);
//
//    while(!q.empty()){
//        x=q.front();
//        for(auto vecin: L[x]){
//            if(!viz[vecin]){
//                viz[vecin]=1;
//                q.push(vecin);
//                dist[vecin]=dist[x]+1;
//            }
//        }
//        q.pop();
//    }
//
//}
//
//
//int main(){
//
//    ifstream cin("bfs.in");
//    ofstream cout("bfs.out");
//
//    int n,m,s;
//    cin>>n>>m>>s;
//
//    for(int i=1; i<=n; i++){
//        dist[i]=-1;
//    }
//
//    for(int i=0; i<m; i++){
//        int x,y;
//        cin>>x>>y;
//        L[x].push_back(y);
//    }
//
//    BFS(s);
//
//    for(int i=1; i<=n; i++){
//        cout<<dist[i]<<" ";
//    }
//
//    return 0;
//}

//BERARII

//vector <int> L[1000001];
//queue <int> q;
////int P[100001];
//vector <int> rasp;
//int viz[1000001];
//
////varianta cu bfs
////void BFS(int x, int &ok){
////    int vis[100001]={0};
////    vis[x]=1;
////    q.push(x);
////
////    while(!q.empty()){
////        x=q.front();
////        for(auto vecin: L[x]){
////            if(!vis[vecin]){
////                q.push(vecin);
////                vis[vecin]=1;
////                if(P[vecin]){
////                    ok=1;
////                }
////            }
////
////        }
////        q.pop();
////    }
////
////}
//
//void DFS(int x){
//    viz[x]=1;
//    for(auto vecin: L[x]){
//        if(!viz[vecin]){
//            DFS(vecin);
//        }
//    }
//}
//
//
//int main(){
//
//    ifstream cin("berarii2.in");
//    ofstream cout("berarii2.out");
//
//    int n,m,p;
//    cin>>n>>m>>p;
//
//    for(int i=0; i<m; i++){
//        int x,y;
//        cin>>x>>y;
//        L[y].push_back(x);
//    }
//
//    for(int i=1; i<=p; i++){
//        int b;
//        cin>>b;
////        P[b]=1;
//        DFS(b);
//    }
//
//
//    int nr=0;
//
//    for(int i=1; i<=n; i++){
//        if(!viz[i]){
//            rasp.push_back(i);
//            nr++;
//        }
//    }
//
//
//    //varianta cu BFS
////    for(int i=1; i<=n; i++){
////        int ok=0;
////
////        if(P[i]){
////            ok=1;
////        }
////        else{
////            BFS(i, ok);
////        }
////
////        if(!ok){
////            nr++;
////            rasp.push_back(i);
////        }
////
////    }
//
//
//    cout<<nr<<'\n';
//
//    for(int i=0; i<nr; i++){
//        cout<<rasp[i]<<'\n';
//    }
//
//    return 0;
//}


//componente tare conexe
//vector <int> L[100001];
//vector <int> L_i[100001];
//vector <vector<int>> sol;
//int viz[100001];
//stack <int> st;
//
//void DFS1(int x){
//    viz[x]=1;
//    for(auto vecin: L[x]){
//        if(!viz[vecin]){
//            DFS1(vecin);
//        }
//    }
//    st.push(x);
//}
//
//void DFS2(int x, vector<int> &component){
//    viz[x]=1;
//    component.push_back(x);
//    for(auto vecin: L_i[x]){
//        if(!viz[vecin]){
//            DFS2(vecin, component);
//        }
//    }
//
//}
//
//
//int main(){
//    ifstream cin("ctc.in");
//    ofstream cout("ctc.out");
//
//    int n,m;
//    cin>>n>>m;
//
//    for(int i=0; i<m; i++){
//        int x,y;
//        cin>>x>>y;
//        L[x].push_back(y);
//        L_i[y].push_back(x);
//    }
//
//    for(int i=1; i<=n; i++){
//        if(!viz[i]){
//            DFS1(i);
//        }
//    }
//
//    memset(viz, 0, sizeof(viz));
//
//    while(!st.empty()){
//        int nod=st.top();
//        st.pop();
//        if(!viz[nod]){
//            vector <int> component;
//            DFS2(nod, component);
//            sol.push_back(component);
//        }
//    }
//
//    cout << sol.size() << '\n';
//    for(auto &comp : sol){
//        for(int node : comp){
//            cout << node << " ";
//        }
//        cout << '\n';
//    }
//
//    return 0;
//}

//sortare topologica

vector<int> din;
vector <int> L[100001];
queue <int> q;

int main(){
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

    int n,m;
    cin>>n>>m;

    for(int i=0; i<m; i++){
        int x,y;
        cin>>x>>y;
        L[x].push_back(y);
        din[y]++;
    }

    for(int i=1; i<=n; i++){
        if(din[i]==0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int nod=q.front();
        cout<<nod<<" ";
        q.pop();
        for(auto vecin: L[nod]){
            din[vecin]--;
            if(din[vecin]==0){
                q.push(vecin);
            }
        }
    }
    

    return 0;
}