Cod sursa(job #1602077)

Utilizator George519Stoian George George519 Data 16 februarie 2016 15:07:26
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
/**
Metoda de rezolvare
Nodul care nu depind de nici un alt nod se numeste nod cauza
//Cautam nodurile cauza posibile
le verificam , primul gasit opreste cautarea

Optimizari posibile:
in cauzul unui nod cauza care nu cuprinde toate nodurile
se face o matrice cu relatiile nodurilor(da , lista e mai buna)
*/
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
unsigned int n,m;
unsigned int a[10000][10000];
unsigned int i;
unsigned int x,y;
unsigned int cauza_list[10000];
int k=0;
int viz[10000];
int corect=0;

unsigned int sol[10000];

void tipar()
{
    unsigned int i ;
    for(i=1;i<=n;i++)
        g<<sol[i]<<" ";
}

void df_recurs(int virf)
{int i;
k++;
sol[k]=virf;
   for(i=1;i<=n;i++)
        if(a[virf][i]==1&&viz[i]==0) {
            viz[i]=1;
            df_recurs(i);
            }
if(k==n) corect=1;
}

int main()
{
f>>n;
f>>m;
for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[y][0]=1;///nu este nod primar pentru ca depinde de x
        a[x][y]=1;
    }
     corect=0;
for(i=1;i<=n;i++)
if(a[i][0]==0)
    {///elementul i este cauza si il trecem prin df ca sa ver daca e bun
        viz[i]=1;
        df_recurs(i);
        if(corect==1) {tipar();///vector sol retine parcurgere df
                        ///oprim for
                        }
                viz[i]=0;
                }
f.close();
g.close();
    return 0;

}