de toate pentru teza

//afisati toate drumurile dintre x si y
// afisati toate drumurile de lungime n;

#include <iostream>
#include <cstring>
#include <fstream>
#include <stdlib.h>


using namespace std;

ifstream fin("date.in");
ofstream fout ("date.out");
int x,y;
int st[100], a[100][100];
int n;
void afisare (int k)
{
    cout<<endl;
    for (int i=1;i<=k;i++)
        {
            cout<<st[i];

        }
}

void citire ()
{
    char sir[100];
    char *p;
    int nr;
    for (int i=1;i<=n;i++)
    {
        fin.getline(sir,100);
        p=strtok(sir," ");
        while (p)
        {
            nr=atoi(p);
            a[nr][i]=a[i][nr]=1;
            p=strtok(NULL," ");
        }
    }
}

int valid (int k)
{
    for (int i=1;i<k;i++)
        if (st[k]==st[i])
            return 0;
        if (k>1 && a[st[k]][st[k-1]]==0)
            return 0;
    return 1;
}

void back (int k)
{
    for (int i=1;i<=n;i++)
   {
       st[k]=i;
        if (valid (k))
            if (st[k]==y) // schimb aici daca k==n atunci afiseaza toate nodurile de lungime n si afiseaza drumu
                afisare (k);
                else
                    back (k+1);
   }
}

int main ()
{

    fin>>n;
    citire();
    fin>>x>>y;
    st[1]=x; // ca sa afisam drumurile de lungime x nu mai trbe asta
    back(2); // back de la 1 daca vrem sa vedem toate drumurile de drum n
    return 0;
}


______________________________________________________________________________________________________________________

// n noduri m muchii
// gradul unui nod, toate drumurile dintre doua noduri x si y citite de la tastatura
// toate nodurile izolate, toate nodurile de grad maxim
//gradul unui grad == suma celor de 1 de pe linia gradului
// daca este drum intre nodurile memorate in p(100)
#include <iostream>
#include <fstream>
using namespace std;
int a[100][100], n , m , st[100],d[100],x,y,drum[100],p[100];
int nod1, nod2;
ifstream fin ("date.in");

void citire ()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++ )
    {
        fin>>x>>y;  // x si y este legatura...
        a[x][y]=a[y][x]=1;
    }
}

void grade ()
{
    for (int i=1;i<=n;i++)  // parcurg prima linie
        for (int j=1;j<=n;j++)
            d[i]=d[i] + a[i][j]; // calculez numaru de legaturi si le bag intrun vector
}

void afisare (int k)
{

    cout<<endl;
    cout<<"un drum este : ";
    for (int i=1;i<=k;i++)
        cout<<st[i]<<" ";// in st[i] se imprima drumul
}

int valid (int k)
{
    for (int i=1;i<k;i++)
        if (st[i]==st[k])
            return 0;
    if (k>1 && a[ st[k] ][ st[k-1] ]==0 ) // daca nu este legatura intre nodul k si k-1 returnez 0;
        return 0;
    return 1;
}


void back (int k)
{
    for (int i=1;i<=n;i++)
    {
        st[k]=i;
        if (valid (k)) // verific daca este legatura si daca este cel mai scurt drum.
            if (st[k]==nod2) // inseamna ca a ajuns
                afisare (k);
            else back (k+1);
    }

}

void drumuri ()
{

    fin>>nod1>>nod2; // se citeste punctul initial si destinatia
    st[1]=nod1; // se baga primul nod in stiva
    back (2);

}

int main()
{
    int mini=-9;
    citire (); // citesc nr de muchii si nr de noduri.
    grade() ; // calculez cate muchii is legate de fiecare nod
    int i;
    for ( i=1;i<=n;i++)  // caut valoarea maxima de legaturi la 1 nod
    {
        if (d[i]>mini)
            mini=d[i];
    }
    for (i=1;i<=n;i++)  // caut toate valorile egale cu valoarea maxima
    {
        if (d[i]==mini)
            cout<<i<<" , "; // afisez i care este nodul implicit
    }
    cout<<endl;
    cout<<"izolatu este";
    for (i=1;i<=n;i++)  // caut pe ce linie este tot = 0... ca sa vad care este izolat
    {

        if (d[i]==0)
        cout<<i;
    }
    cout<<endl;
    drumuri ();
    int pp; // pp este numarul de noduri care o sa verific
    cin>>pp;
    for (int i=1; i<=pp ; i++)
    {
        cin>>p[i]; // citesc drumul
    }
    int ok=0;
    for (int i=1 ; i<pp ;i++) // pp este numarul de noduri, sa vad daca este drum intre ele
    {
        if (a[ p[i] ][ p[i+1] ] == 1) // verific daca este legatura intre 2 alaturate
            continue; // daca este continui
        else
            {
                cout<<"nu este drum"; // daca nu este afisez ca nu este
                ok++; // incrementez ok
                break;

            }
    }
    if (ok==0) // daca ok nu este marit inseamna ca este drum
    cout<<"este drum";


_______________________________________________________________________________________________________________________

backtracking recursiv

// toate modurile de a da o serie de examene ca sa obtina creditele de care are nevoie

#include <iostream>
using namespace std;

int st[100],n,s,S,a[100];

void afisare (int k)
{
    cout<<"o solutie este";
    for (int i=1;i<=k;i++)
    {
        cout<<a[st[i]]<<"+";
    }
}
void citire ()
{
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
}

int valid (int k)
{
    S=0;
    for (int i=1;i<k;i++)
       {
           if (st[i]==st[k])
            return 0;
        S=S+a[st[i]];
       }
       S=S+a[st[k]];
    return 1;
}

void back (int k)
{
    for (int i=1;i<=n;i++)
    {
        st[k]=i;
        if (valid(k))
            if(S>=s)
                afisare (k);
        else back (k+1);
    }
}

int main ()
{
    cout<<"cate examene"; cin>>n;
    cout<<"cate credite"; cin>>s;
    citire ();
    back (1);
    return 0;
}

_______________________________________________________________________________________________________________________

/*
    se citeste un nr n. generam toate posibilitatie de-al exprima pe n ca .
    toate numerele de la 1 la n : ex:   5= -1+2+3-4+5
*/
#include <iostream>

using namespace std;

int st[100], n;

void afisare (int k)
{
    cout<<"\n o solutie este :";
    for (int i=1;i<=n;i++)
    {
        if (st[i]==-1)
        cout<<"-"<<i;
        else
        cout<<"+"<<i;
    }

}

int valid (int k)
{
    int s=0;
    if (k==n)
    {
        for (int i=1;i<=k;i++)
            s=s+i*st[i];
        if (s!=n)
            return 0;
    }
    return 1;
}

void back (int k)
{
    for (int i=-1;i<=1;i+=2)
    {
        st[k]=i;
        if (valid (k))
            if (k==n)
                afisare (k);
            else
            back (k+1);
    }
}

int main()
{
    cout<<"baga n";
    cin>>n;
    back(1);
    return 0;
}

_________________________________________________________________________________________________

ROYFLOYD            matricea costurilor.

{
    int k,i,j;
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                if (a[i][j]==0||a[i][j]>a[i][k]+a[k][j])
                    a[i][j]=a[i][k]+a[k][j];
}

DFS

void DFS(int nod_curent)
{
    cout<<nod_curent<<"\t";
    for (i=1;i<=n;i++)
    if(a[nod_curent][i] && !viz[i])
        DFS[i];
}