Cod sursa(job #3260056)

Utilizator iustin948Homoranu Iustin iustin948 Data 29 noiembrie 2024 20:06:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;


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

vector< vector< int> > graph;
vector<int> degree;
int n , m;
void read()
{
    fin >> n >> m;
    graph.resize(n+1);
    degree.resize(n+1);
    int x, y;
    for(int i = 0; i < m; i++)
    {
        fin >> x >> y;
        graph[x].push_back(y);
        degree[y]++;
    }
}

void solve()
{
    queue <int> q;
    int node = 0;
    for(int i = 1; i <= n; i++)
        if(degree[i] == 0)
               q.push(i);




    for(int i = 1; i <= n; i++)
    {
        node = q.front();
        q.pop();
        fout << node << " ";
        for(auto w : graph[node])
            {
                degree[w]--;
                if(degree[w] == 0)
                    q.push(w);

            }
    }
    fout << "\n";
}

int main()
{
    read();
    solve();
    return 0;
}