Cod sursa(job #681868)

Utilizator dandroidDan Octavian dandroid Data 17 februarie 2012 22:54:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "sortaret.in"
#define OUT "sortaret.out"

//#define ONLINE_JUDGE

static const int MAX_NODES = 50100;
static const int MAX_EDGES = 100000;
int nodeCount;
int edgeCount;
int incoming[MAX_NODES];
queue<int> noParentNodes;

list<int> neighbors[MAX_NODES];
list<int> sortedNodes;

void buildGraph ()
{
  int x, y;
  for (int i = 0; i < edgeCount; i++)
  {
    cin >> x >> y; 
    neighbors[x].push_back(y);
    incoming[y]++;
  }  

}

void topSort()
{
  for (int i = 1; i <= nodeCount; i++)
  {
    if (incoming[i] == 0)
    {
      noParentNodes.push(i);
    }
  }

  while (!noParentNodes.empty())
  {
    int node = noParentNodes.front();
    noParentNodes.pop();

    list<int>::iterator it;
    list<int>* neighs = &neighbors[node];
    for (it = neighs->begin(); it != neighs->end(); it++)
    {
      if (incoming[*it] > 0)
      {
        incoming[*it]--;
        if (incoming[*it] == 0)
        {
          noParentNodes.push(*it); 
        }
      } 
    }
    sortedNodes.push_back(node);
  }

  list<int>::iterator it;
  for (it = sortedNodes.begin(); it != sortedNodes.end(); it++)
  {
    cout << *it << " "; 
  }
}
vector<list<int>*>* graph;
void solve(int test) {
  cin >> nodeCount; 
  cin >> edgeCount;
  buildGraph();
  topSort();
}

int main() {
#ifndef ONLINE_JUDGE
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
#endif
    solve(0);
    return 0;
}