Cod sursa(job #1404953)

Utilizator cautionPopescu Teodor caution Data 28 martie 2015 18:19:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    long *out_order, *sorted;
    long n, m, a, b;
    queue<long> Q;
    vector<long> *graf;
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    in>>n>>m;
    out_order = new long[n+1];
    graf = new vector<long>[n+1];
    sorted = new long[n+1];
    sorted[0]=0;
    for(long i=1; i<=n; ++i)
        out_order[i]=0;
    for(long i=0; i<m; ++i)
    {
        in>>a>>b;
        ++out_order[b];
        graf[a].push_back(b);
    }
    for(long i=1; i<=n; ++i)
        if(!out_order[i])
            Q.push(i);
    while(!Q.empty())
    {
        a=Q.front();
        Q.pop();
        ++sorted[0];
        sorted[sorted[0]]=a;
        for(vector<long>::iterator it=graf[a].begin(), ed=graf[a].end(); it!=ed; ++it)
        {
            --out_order[*it];
            if(!out_order[*it]) Q.push(*it);
        }
    }
    for(long i=1; i<=sorted[0]; ++i)
        out<<sorted[i]<<' ';
    in.close(); out.close();
    return 0;
}