Cod sursa(job #2798345)

Utilizator VladCaloVlad Calomfirescu VladCalo Data 11 noiembrie 2021 10:40:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
// #include <iostream>
// #include <fstream>
// #include <stack>
// #include <vector>

// using namespace std;

// ifstream fin("sortaret.in");
// ofstream fout("sortaret.out");


// vector<vector<int> > adj;
// stack <int > mystack;
// vector <bool> visited;

// // void dfs (int nod){
// //     visited[nod] = true;
// //     for (int i = 0; i < adj[nod].size(); i++)
// //     {
// //         int curr = adj[nod][i];
// //         if (visited[curr] == false)
// //             dfs(curr);
// //     }
// //     mystack.push(nod);
// // }
// void dfs1(int nod) //dfs normal
// {
//     visited[nod] = true;
//     for (int i = 0; i < adj[nod].size(); i++)
//     {
//         int curr = adj[nod][i];
//         if (visited[curr] == false)
//             dfs1(curr);
//     }
//     mystack.push(nod); // se pun in stack nodurile parcurse
// }


// int n, m,x,y;
// int main(){
//     fin>> n >> m;
//     adj = vector<vector<int> >(n + 1);
//     for (int  i=1;i<=m;i++){
//         fin>>x>>y;
//         adj[x].push_back(y);
//     }

//     for (int i=1;i<=n;i++){
//         if (visited[i]==false){
//             dfs1(i);
//         }
//     }

//     while (!mystack.empty()){
//         fout<<mystack.top()<<" ";
//         mystack.pop();
//     }


//     return 0;
// }

#include <iostream>
#include <fstream> 
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
 

 vector <vector<int> > adj;
 vector <bool> visited;
 stack <int > mystack;

 void dfs(int nod) 
{
    visited[nod] = true;
    for (int i = 0; i < adj[nod].size(); i++)
    {
        int curr = adj[nod][i];
        if (visited[curr] == false)
            dfs(curr);
    }
    mystack.push(nod); // 
}
int main() {
 int n, m, x, y;
    fin >> n >> m;
    adj = vector<vector<int> >(n + 1);  // adiacenta

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        adj[x].push_back(y);
    }

    for (int i=1; i <= n; i++){
        if (visited[i]==false){
            dfs(i);
        } 
    }

    while (!mystack.empty()){
        fout<<mystack.top()<<" ";
        mystack.pop();
    }
    return 0;

}