Mali zadatak u C++

Ja se ne mogu sjetiti nicega osim klasicnog matchinga sto je O ( N^3 ) algoritam gdje je N broj sahista.

Dakle koliko kola imas, jasno je da ih imas N-1.

dakle trebas :

bool par[ MAXN ][ MAXN ] : array koji ce ti reci je li taj par vec bio igran

int uzeo[ MAXN ] : array koji ce ti reci za svako kolo s kime igra x-ti igrac : uzeo[x] -> s kime igra igrac x, a uzeo[uzeo[x]] == x, to je jasno ...

array uzeo refreshas nakon svakog kola i to ti je to...

EDIT : trebas rabiti backtrack, dfs tipa. No slozenost ostaje O ( N^3 ) jer se dfs ponasa kao jos jedna for petlja.

Evo implementacija algoritma kojeg sam gore objasio ...

Mozda malo spor, ali radi.

#include <cstdio>
#include <cstring>

bool par[ 100 ][ 100 ], out[ 100 ];
int  uzeo[ 100 ];
int  N;

bool dfs(int p)
{
    if (p > N) return 1;
    if (uzeo[p]) return dfs(p+1);

    for (int i = 1; i <= N; ++i) {
       if (uzeo[i]) continue;
       if (par[i][p] || i == p) continue;
       uzeo[p] = i;
       uzeo[i] = p;
       if (dfs(p+1)) return true;
       uzeo[p] = 0;
       uzeo[i] = 0;
    }
    return false;
}

int main()
{
    memset(par, 0, sizeof par);

    scanf("%d", &N);
    for (int i = 1; i < N; ++i) {
       for (int j = 1; j <= N; ++j)
          uzeo[j] = out[j] = 0;
       dfs(1);
       printf("KOLO : %d\n", i);
       for (int j = 1; j <= N; ++j) {
          if (!out[j]) printf("%d vs %d\n", j, uzeo[j]);
          par[j][uzeo[j]] = 1;
          out[uzeo[j]] = 1;
          out[j] = 1;
       }
    }
}

EDIT : Dodano da ispisuje jedan par samo jedanput, napr. ispise  1 vs 2, ali ne i 2 vs 1.

Daj mi primjer gdje netko igra protiv 0, koliko ja vidim to se dogadja samo pri neparnim brojevima, a u zadatku kaze samo PARNI brojevi. Bas me interesira kao bi ti organizirao ligu sa neparnim brojem klubova ...

Aki igrac 1 igra protiv igraca 2 u 1. kolu tada igrac 2 ne igra protiv ikoga drugoga nego protiv 1, ako bas oces mogu ubaciti jos jedan array da makne taj "mistake".

EDIT : Evo dodao sam i to.

Ok, sry ...

Evo jedno pitanjce na brzinu.

Ja bih počeo programirati u c++, tj. za par dana stiže mi knjige c++: analiza i primjena pa me zanima koji program da instaliram za programiranje u c++? (visual studio c++?)

I da, koji mi svi programi trebaju za programiranje, znači da mogu kod spremat kao .exe i da sve normalno radi?

Unaprijed hvala, i molio bih vas bez ismijavanja ;)

Aha, ali visual c++ ima i kompajler i sve što mi treba.

Budimire hvala na sastavljanju algoritma :)

Napisao bi ranije zahvalu ali nisam bio pri računalu zbog privatnih problema.

e sad imam jos jedan problemcic,a to je da kad C/P ovaj program sto si napisao meni se nista ne događa.unesem broj parova i program se ugasi

Tracer je upravu, nema smisla. Ja pisem poprilicno naprednu implementaciju algoritma, a ti niti program ne znas pokrenuti ...

Ja sam prvo imao namjeru samo opisati algoritam sto sam napravio u prvom postu, no kasnije sam i sam htio implementirati rjesenje.

Bio sam uvjeren da autor teme zna programirati jer ovakav zadatak nije bas namjenjen pocetnicima ...

Ako je neparan broj, dodas jos jednog (fiktivnog) igraca da bude paran broj, izvrtis algoritam, i uzmes da tko god igra s tim fiktivnim  igracem, u stvari pauzira tu rundu.