Cod sursa(job #3252330)

Utilizator Victor5539Tanase Victor Victor5539 Data 29 octombrie 2024 11:00:15
Problema Dusman Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <set>

using namespace std;
ifstream fin("dusman.in");
ofstream fout("dusman.out");

int n,k,m,v[1005],i,j,f[1005],nr;
bool ok=0;
set <int> s[1005];

void afis()
{
    for (int i=1; i<=n; i++)
        fout<<v[i]<<" ";
    fout<<"\n";

    ok=1;
}

void bkt(int pas)
{
    if (ok)
        return;

    if (pas==1)
    {
        for (int i=1; i<=n; i++)
        {
            f[i]=1;
            v[pas]=i;
            if (pas<n)
                bkt(pas+1);
            else
            {
                nr++;
                if (nr==k)
                    afis();
            }
            f[i]=0;
        }
    }
    else
    {
        for (auto x: s[v[pas-1]])
        {
            if (f[x]==0)
            {
                v[pas]=x;
                f[x]=1;
                if (pas<n)
                    bkt(pas+1);
                else
                {
                    nr++;
                    if (nr==k)
                        afis();
                }
                f[x]=0;
            }
        }
    }
}

int main()
{
    fin>>n>>k>>m;

    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            if (i!=j)
                s[i].insert(j);
    }

    while (m)
    {
        int a,b;
        fin>>a>>b;
        s[a].erase(b);
        s[b].erase(a);
        m--;
    }

    bkt(1);
    return 0;
}