Cod sursa(job #2798364)

Utilizator VladCaloVlad Calomfirescu VladCalo Data 11 noiembrie 2021 11:00:49
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb


// #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<int> adj[100001];
//  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;

// }


#include <iostream>
#include <fstream> 
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
 
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
 
const int maxN = 5e4 + 5;
 
vector <int> g[50001];
stack <int> top;
bool check[50001];
 
void dfs(int node) {
    check[node] = true;
    for(int next=1;next<g[node].size();next++ )
        if(check[next] == false)
            dfs(next);
    top.push(node);
}
 
int main()
{
    int n, m; fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v; fin >> u >> v;
        g[u].push_back(v);
    }
       
    for(int i = 1; i <= n; ++i) {
        if(check[i] == false)
        dfs(i);
    }
    
    while(!top.empty()) {
        fout<<top.top()<<" ";
        top.pop();
    }
 
    return 0;
}