Pagini recente » Cod sursa (job #1986176) | Cod sursa (job #1378367) | Cod sursa (job #285733) | Cod sursa (job #3196302) | Cod sursa (job #1602077)
/**
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;
}