Cod sursa(job #2145227)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 27 februarie 2018 10:44:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

struct nod {
    int inf;
    nod *urm;
}*l[50005];

int n,m,viz[50005],st[50005],nr;

void adaug(nod*&p,int x) {
    nod *c;
    c=new nod;
    c->urm=p;
    c->inf=x;
    p=c;
}

void df(int k) {
    nod *c;
    viz[k]=1;
    for (c=l[k];c;c=c->urm)
        if (!viz[c->inf])
            df(c->inf);
    st[++nr]=k;
}

int main() {
    int i,x,j,y,ok;
    nod *c;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y;
        ok=1;
        for (c=l[x];c;c=c->urm)
            if (c->inf==y) {
                ok=0;
                break;
            }
        if (ok)
            adaug(l[x],y);
    }
    for (i=1;i<=n;i++)
        if (!viz[i])
            df(i);
    for (i=n;i>=1;i--)
        g<<st[i]<<' ';
    return 0;
}