Cod sursa(job #1419837)

Utilizator mariusadamMarius Adam mariusadam Data 16 aprilie 2015 20:45:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 50001

using namespace std;
vector <int> G[nmax];
int n,m;

void readData(vector <int> (&G)[nmax],int &n,int &m) {

    ifstream r("sortaret.in");
    r>>n>>m;
    for (int k=1;k<=m;k++) {
        int i,j;
        r>>i>>j;
        G[i].push_back(j);
        }
    r.close();
}

void df(vector <int> (&G)[nmax],vector <int> &tps,bool (&viz)[nmax],int nod) {
    viz[nod]=true;
    for (vector <int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
        if (!viz[*it])
            df(G,tps,viz,*it);

    tps.push_back(nod);
}
void sorteaza_top(vector <int> (&G)[nmax],int n,vector <int> &tps) {
    bool viz[nmax];

    memset(viz,false,sizeof(viz));

    for (int i=1;i<=n;i++)
        if (!viz[i])
            df(G,tps,viz,i);
}

void writeData(vector <int> &tps) {

    ofstream w("sortaret.out");
    for (unsigned int i=tps.size();i>0;i--)
        w<<tps[i-1]<<" ";
    w.close();
}

int main() {
    vector <int> tps;
    readData(G,n,m);
    sorteaza_top(G,n,tps);
    writeData(tps);
    return 0;
}