Cod sursa(job #2660420)

Utilizator lauratenderLaura Tender lauratender Data 19 octombrie 2020 11:54:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    int N, M, x1, x2;
    in >> N >> M;

    vector<vector<int>> adj(N + 1); //listele de adiacenta
    vector<int> deg(N + 1, 0);  // gradele nodurilor
    vector<int> q; // folosesc un vector drept coada pentru sortarea topologica

    for (int i = 0; i < M; ++i)
    {
        in >> x1 >> x2;
        adj[x1].push_back(x2); //adaug muchie in lista
    }

    // aflu gradul initial al fiecarui nod
    for (int i = 1; i <= N; ++i)
      for (auto j : adj[i])
        ++deg[j];

    int first = 0, last = 0;
    for (int i = 1; i <= N; ++i)
      if (deg[i] == 0)
      {
          q.push_back(i); // daca un nod are gradul 0 il adaug in coada
          ++last;
      }

    while(first <= last)
    {
      int node = q[first];
      ++first;
      for (int nbh : adj[node])
      {
        --deg[nbh];
        if (deg[nbh] == 0)
        {
          q.push_back(nbh);
          ++last;
        }
      }
    }
    for ( int i = 0; i < last; ++i)
        out << q[i] <<" ";
    return 0;
}