Cod sursa(job #928808)

Utilizator vladm97Matei Vlad vladm97 Data 26 martie 2013 18:26:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include<iostream>
#include<vector>
#include<string.h>
#define lmic 60000
#define lmare 200000
#include<cstdlib>
using namespace std;

class graf{
private:
    int n;
    int s;
    int m;
    vector<int>v[lmic];
    int *tata;
    int *parcurs;
    char *fin;
    char *fout;
    int *sol;
public:
    graf(char*,char*);
    ~graf();
    void df(int);
    void tati();
    void sp();
};

graf::graf(char*in,char*out){
tata=(int*)calloc(lmic,sizeof(int));
fin=new char[strlen(in)+1];
strcpy(fin,in);
fout=new char[strlen(out)+1];
strcpy(fout,out);
parcurs=(int*)calloc(lmic,sizeof(int));
sol=(int*)calloc(lmic,sizeof(int));
}

graf::~graf(){
delete[] tata;
delete[] fin;
delete[] fout;
delete[] parcurs;
delete[] sol;
}

void graf:: df(int a){
    parcurs[a]=1;
for(int i=0;i<v[a].size();i++)
    if(parcurs[v[a][i]]==0)
        df(v[a][i]);
sol[s++]=a;}

void graf:: tati(){
for(int i=1;i<=n;i++)
    if(tata[i]==0)df(i);
}

void graf:: sp(){
ifstream f(fin);
ofstream g(fout);
int i,a,b;
f>>n;
f>>m;
for(i=1;i<=m;i++){
    f>>a>>b;
    v[a].push_back(b);
    tata[b]=1;
}
tati();
s--;
for(i=s;i>=0;i--)
    g<<sol[i]<<" ";
}


int main()
{
   graf A("sortaret.in","sortaret.out");
   A.sp();
}