Cod sursa(job #1691340)

Utilizator pulseOvidiu Giorgi pulse Data 18 aprilie 2016 00:50:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 50000 + 1;

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

int n, m;
vector<vector<int> > g;
vector<int> grad;
queue<int> q;

void sortaret()
{
  for (int i = 0; i < n; ++i) {
    if (!grad[i]) {
      q.push(i);
      fout << i + 1 << " ";
    }
  }

  while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (vector<int>::iterator it = g[node].begin(); it != g[node].end(); ++it) {
      grad[*it]--;
      if (!grad[*it]) {
        q.push(*it);
        fout << *it + 1 << " ";
      }
    }
  }
}

int main()
{
  fin >> n >> m;

  g.resize(n);
  grad.resize(n, 0);
  for (int i = 1, x, y; i <= m; ++i) {
    fin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    grad[y]++;
  }

  sortaret();

  return 0;
}