Tema 7 feb 2020

---------------------------------------Turneu----------------------------
#include <iostream>

using namespace std;

bool a[105][105],viz[105],gasit;
int n,st[105];

void citire()
{
    int m,x,y;
    cin>>n;
    m=n*(n-1)/2;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        a[x][y]=1;
    }
}

void afisare()
{
    for (int i=1;i<=n;i++)
        cout<<st[i]<<' ';
    gasit=true;
}

void bck(int k)
{
    for (int i=1;i<=n && !gasit;i++)
    {
        st[k]=i;
        if (a[st[k-1]][i] && !viz[i] || k==1)
            if (k==n)
                afisare();
            else
            {
                viz[i]=1;
                bck(k+1);
                viz[i]=0;
            }
    }
}

int main()
{
    citire();
    bck(1);
    return 0;
}

-----------------------------------------Drumuri-----------------------------------------
#include <iostream>

using namespace std;

int n,viz[105],p;
bool a[105][105];

void citire()
{
    int m,x,y;
    cin>>n>>p>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        a[x][y]=1;
    }

}

void DFS(int p, int k)
{
    viz[p]=k;
    for (int i=1;i<=n;i++)
        if (a[p][i] && (!viz[i] || viz[i]>k))
            DFS(i,k+1);
}

void afisare()
{
    int v[105],k=0;
    for (int i=1;i<=n;i++)
        if (viz[i]%2==0 && viz[i]>2)
            v[++k]=i;
    cout<<k<<'\n';
    for (int i=1;i<=k;i++)
        cout<<v[i]<<' ';
}

int main()
{
    citire();
    DFS(p,2);
    afisare();
    return 0;
}

-------------------------------------------Anunt--------------------------------------------
#include <iostream>
#include <cstring>

using namespace std;

bool a[105][105],viz[105];
int n;

void citire()
{
    int m,x,y;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        a[x][y]=1;
    }
}

void Fill(int x)
{
    viz[x]=1;
    for (int i=1;i<=n;i++)
        if (a[x][i] && !viz[i])
            Fill(i);
}

bool verif()
{
    for (int i=1;i<=n;i++)
        if (!viz[i])
            return false;
    return true;
}

void rezolvare()
{
    for (int i=1;i<=n;i++)
    {
        Fill(i);
        if (verif())
            cout<<i<<' ';
        memset(viz,0,105);
    }
}

int main()
{
    citire();
    rezolvare();
    return 0;
}

--------------------------------Drum Hamiltonian--------------------------------------------------
#include <fstream>

using namespace std;

ifstream f("drum_hamiltonian.in");
ofstream g("drum_hamiltonian.out");

int n,st[15];
bool a[15][15],gasit;

void citire()
{
    int x,y;
    f>>n;
    while(f>>x>>y)
        a[x][y]=1;
}

bool diferit(int k)
{
    for (int i=1;i<k;i++)
        if (st[i]==st[k])
            return false;
    return true;
}

void afisare()
{
    gasit=true;
    g<<1<<'\n';
    for (int i=1;i<=n;i++)
        g<<st[i]<<' ';
}

void bck(int k)
{
    for (int i=1;i<=n && !gasit;i++)
    {
        st[k]=i;
        if ((k==1 || a[st[k-1]][i]) && diferit(k))
        {
            if (k==n)
                afisare();
            else
                bck(k+1);
        }
    }
}

int main()
{
    citire();
    bck(1);
    if (!gasit)
        g<<'0';
    return 0;
}