Cod sursa(job #2277482)

Utilizator maria15Maria Dinca maria15 Data 6 noiembrie 2018 12:54:12
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, i, a, b, f[50003], p, u, c[50003], crt, g[50002];
vector<int> v[50004];

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

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
        f[b]++;
    }
    for(i=1;i<=n;i++)
        if(f[i] == 0){
            /// bfs
            p = u = 1;
            c[1] = i;
            g[i] = 1;
            fout<<i<<" ";
            while(p <= u){
                crt = c[p];
                sort(v[crt].begin(), v[crt].end());
                for(int j = 0;j<v[crt].size();j++)
                    if(g[v[crt][j]] == 0){
                    fout<<v[crt][j]<<" ";
                    c[++u] = v[crt][j];
                    g[v[crt][j]] = 1;
                }
                p++;
            }
            return 0;
        }
    return 0;
}