Cod sursa(job #1939790)

Utilizator bmanghiucManghiuc Bogdan bmanghiuc Data 26 martie 2017 00:15:35
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool viz[500005];

int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    int n, m;
    f>>n>>m;

    vector<int> edges[n+1];
    vector<int> traverse;
    vector<int> parent;

    for(int i=0; i<=n; i++){
        parent.push_back(-1);
    }

    int x, y;
    for(int i=1; i<=m; i++){
        f>>x>>y;
        parent[y] = x;
        edges[x].push_back(y);
    }


    for(int i=1; i<=n; i++){
        if(parent[i] == -1){
            stack<int> q;
            q.push(i);
            int current;
            while(! q.empty()){
                current = q.top();
                q.pop();
                if(viz[current] == true){
                    continue;
                } else{
                    viz[current] = true;
                    traverse.push_back(current);
                    for(int j=0; j<(int)edges[current].size(); j++){
                        if(viz[edges[current][j]] == false){
                            q.push(edges[current][j]);
                        }
                    }
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        g<<traverse[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}