Cod sursa(job #951444)

Utilizator blechereyalBlecher Eyal blechereyal Data 20 mai 2013 16:40:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
using namespace std;
#include <fstream>
#include <vector>
#include <iostream>
#include <string.h>
#include <queue>

int main()
{
    int M,N,x,y,i;
    vector <int> *graph;
    queue <int> Q;
    vector <int> ::iterator it;
    int *grad;

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

    in>>N>>M;
    grad=new int[N+1];
    memset(grad,0,N+1);
    graph=new vector<int> [N+1];
    for (i=1;i<=N;i++) grad[i]=0;

    for (i=1;i<=M;i++)
        {
            in>>x>>y;
            graph[x].push_back(y);
            grad[y]++;
        }

    for (i=1;i<=N;i++)
     if (grad[i]==0) Q.push(i);

    while (!Q.empty())
     {
         x=Q.front();
         out<<x<<" ";
         Q.pop();
         for (it=graph[x].begin();it!=graph[x].end();it++)
            {
            grad[*it]--;
            if (grad[*it]==0) Q.push(*it);
            }
     }

    return 0;
}