Cod sursa(job #802395)

Utilizator ard_procesoareLupicu ard_procesoare Data 26 octombrie 2012 16:55:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100001;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int>  a[N];
queue <int> q;
int n,m,d[N],g,x,y;
void citire()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        d[y]++;
    }
}
void bfs()
{
        int i;
        g=0;
        for(i=1;i<=n;i++)
            if(d[i]==0)
            {
                if(g==0)
                    g=i;
                if(g) fout<<i<<" ";
            }
        q.push(g);
        while(!q.empty())
        {
            x=q.front();
            fout<<x<<" ";
            q.pop();
            for(size_t i=0;i<a[x].size();i++)
            {
                y=a[x][i];
                d[y]--;
                if(d[y]==0) q.push(y);
            }
        }
}

int main()
{
   citire();
   bfs();
}