Cod sursa(job #2062691)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 10 noiembrie 2017 18:46:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

int n, m, x, y;
unsigned int poz;
int v[50005];
vector<int> lista[50005];
vector<int>::iterator it;

void dfs( int nod, vector<int>& stiva ){

    v[nod] = 1;

    for(unsigned int i = 0; i < lista[nod].size(); i++)
        if( v[ lista[nod][i] ] == 0 )
            dfs( lista[nod][i], stiva );

    stiva.push_back( nod );
}

vector<int> sortare(){

    int i;
    vector<int> stiva;

    for(i = 1; i <= n; i++)
        if( v[i] == 0 )
            dfs( i, stiva );

    reverse( stiva.begin(), stiva.end() );

    return stiva;
}

int main()
{

    in>>n>>m;
    for(int i = 1; i <= m; i++){
        in>>x>>y;

        it = lista[x].begin();
        poz = 0;
        while( poz != lista[x].size() && lista[x][poz] < y )
            poz++;
        lista[x].insert(it + poz, y);
    }

    vector<int> st = sortare();

    for(int i = 0; i < st.size(); i++)
        out<<st[i]<<" ";

    return 0;
}