Cod sursa(job #2075875)

Utilizator NacuCristianCristian Nacu NacuCristian Data 25 noiembrie 2017 19:35:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;

vector<int> * citire(int *m, int *n)
{
    int a,b;
    FILE * fin = fopen("sortaret.in","r");

    fscanf(fin,"%d %d",n,m);
    vector<int> * v;
    v= (vector<int> *)malloc((*n)*sizeof(vector<int>));

    for(int i=0;i<*m;i++)
    {
        fscanf(fin,"%d %d",&a,&b);
        v[a-1].push_back(b-1);
    }

    return v;
}


void dfs(int nod, stack <int> *stk, vector<int> * g, bitset<50010> * viz)
{
    for(int i=0;i<(g[nod]).size();i++)
        if((*viz)[g[nod][i]]==0)
        {
            (*viz)[g[nod][i]]=1;
            dfs(g[nod][i],stk,g,viz);
        }
    (*stk).push(nod);
}


stack <int> toposort(vector<int> * g, int m, int n)
{
    bitset <50010> viz;
    stack <int> rez;
    for(int i=0;i<n;i++)
     if (viz[i]==0)
     {
         viz[i]=1;
         dfs(i,&rez,g,&viz);
     }
     return rez;
}

void afisare(stack <int> * rez)
{
    FILE * fout = fopen("sortaret.out","w");
    while(!((*rez).empty()))
    {
        int t=(*rez).top();
        (*rez).pop();
        fprintf(fout,"%d ",t+1);
    }
}

int main()
{
    int m,n;
    vector<int> * g = citire(&m,&n);
    stack <int> rez = toposort(g,m,n);
    afisare(&rez);
    return 0;
}