Cod sursa(job #2225352)

Utilizator NecoaraGabrielNecoara Gabriel-Stefan NecoaraGabriel Data 26 iulie 2018 18:43:26
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb

#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#define Nmax 5005

using namespace std;

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

int N,M, **mat, *viz, *viz2;
int i,j;
void afisare()
{
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
}
void reset()
{
    for(i=1;i<=N;i++)
    {
        viz[i]=0;
        viz2[i]=0;
        for(j=1;j<=N;j++)
            mat[i][j]=0;
    }
}
int main()
{
    int x,y;
    queue<int> Q;
    priority_queue<int, vector<int>, greater<int> > last;
    f>>N;f>>M;

    mat = new int*[N+1];
    viz = new int[N+1];
    viz2 = new int[N+1];
    for(i=0;i<N+1;i++)
        mat[i] = new int[N+1];
    reset();


    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        mat[x][y]=1;
    }

    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
            if(mat[i][j]==1 )
            {
                if(viz2[j]==0)
                {
                    last.push(j);
                    viz2[j]=1;
                }
               if( viz[i]==0)
                {
                    Q.push(i);
                    viz[i]=1;
                }
            }

    }

    while(!Q.empty())
    {
        g<<Q.front()<<" ";
        Q.pop();
    }
    while(!last.empty())
    {
        if(viz[last.top()]==0)
            g<<last.top()<<" ";
        last.pop();
    }
    return 0;
}