Cod sursa(job #914684)

Utilizator tvararuVararu Theodor tvararu Data 14 martie 2013 12:49:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <utility>
using namespace std;

// inline pair<int, int> mp (const int &x, const int &y) {
//   pair<int, int> p;
//   p.first = x; p.second = y;
//   return p;
// }

int main (int argc, char const *argv[])
{
  ifstream in ("sortaret.in");
  
  int n, m; in >> n >> m;
  
  vector< vector<int> > liAd(n + 1);

  vector<int> gradIntern(n + 1);
  
  int x, y;
  while (in >> x >> y) {
    liAd[x].push_back(y);
    gradIntern[y]++;
  }

  // set< pair<int, int> > deg;
  // for (int i = 1; i <= n; i++) {
  //   deg.insert( mp(gradIntern[i], i) );
  // }
  // for (typeof(deg.begin()) it = deg.begin(); it != deg.end(); it++) {
  //   cout << it->first << ' ' << it->second << '\n';
  // }
  
  // for (int i = 1; i <= n; i++) {
  //   // cout << "int: " << gradIntern[i] << ", ext: " << liAd[i].size() << "; ";
  //   cout << i << ": ";
  //   for (unsigned j = 0; j < liAd[i].size(); j++) {
  //     cout << liAd[i][j] << ' ';
  //   }
  //   cout << '\n';
  // }
  // cout << '\n';
  
  queue<int> coada;
  vector<bool> visited(n + 1);
  fill (visited.begin(), visited.end(), 0);
  
  for (int i = 1; i <= n; i++) {
    if (gradIntern[i] == 0) {
      coada.push(i);
      visited[i] = true;
    }
  }
  
  ofstream out ("sortaret.out");
  while (!coada.empty()) {
    int nod = coada.front();
    coada.pop();
    out << nod << ' ';
    
    for (unsigned i = 0; i < liAd[nod].size(); i++) {
      gradIntern[liAd[nod][i]]--;
      if (gradIntern[liAd[nod][i]] == 0 && !visited[liAd[nod][i]]) {
        // cout << liAd[nod][i] << '\n';
        coada.push(liAd[nod][i]);
        visited[liAd[nod][i]] = true;
      }
    }
  }
  out.close();
  
  return 0;
}