Cod sursa(job #1357110)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 23 februarie 2015 19:33:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int N=50005, M=100001;
int n,nrm,nr;
vector<int> v[50005];
queue<int> q;
int lst[N], vf[M], urm[M], m,c[N];
bool viz[50005];

void dfs(int x)
{
    int p = lst[x], y;
    viz[x] = true;
    while(p != 0)
    {
        y = vf[p];
        if (!viz[y])
            dfs(y);
        p = urm[p];
    }
    c[++nr] = x;
}

void adaug(int x, int y)
{
    m++;
    vf[m] = y;
    urm[m] = lst[x];
    lst[x] = m;
}

/*
adaug (2,5), (2,8), (3,6), (2,3)
lst = (0,4,3,...)
vf = (5,8,6,3)
urm = (0,1,0,2)
*/

int main()
{
    int i,j,x,y,cod,p,nod;
    in>>n>>nrm;
    for(i=1;i<=nrm;i++){
        in>>x>>y;
        cod=1;
        p = lst[x];
        while(p != 0)
        {
            nod = vf[p];
            p = urm[p];
            if(nod==y)
                cod=0;
        }
        if(cod==1)
            adaug(x,y);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    for(i=nr;i>=1;i--)
        out<<c[i]<<" ";
    return 0;
}