Cod sursa(job #2302382)

Utilizator BogdanIonesqBogdan Ionescu BogdanIonesq Data 14 decembrie 2018 15:40:24
Problema Dusman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <cstdlib>

using namespace std;

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

int generated = 0;
int n, k, m;

void rec (int poz, int n, vector <int> &v, vector <int> &used, vector < pair <int, int> > &dusmani) {
    if (poz == n + 1) {
        generated++;

        if (generated == k) {
            for (int i = 0; i < v.size(); i++) {
                fout << v[i] << ' ';
            }
            exit(0);
        }
        return;
    }


    for (int elem = 1; elem <= n; elem++) {
        if (used[elem] == 1) {
            continue;
        }

        if (poz == 1) {
            v.push_back(elem);
            used[elem] = 1;

            rec(poz + 1, n, v, used, dusmani);

            v.pop_back();
            used[elem] = 0;

            continue;
        }

        bool ok = true;
        for (int j = 0; j < dusmani.size(); j++) {
            if ( (dusmani[j].first == elem && dusmani[j].second == v.back()) ||
                (dusmani[j].first == v.back() && dusmani[j].second == elem)) {
                    ok = false;
                    break;
                }
        }

        if (ok || poz == 1) {
            v.push_back(elem);
            used[elem] = 1;

            rec(poz + 1, n, v, used, dusmani);

            v.pop_back();
            used[elem] = 0;
        }
    }
}

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

    vector <int> v;
    vector < pair <int, int> > dusmani;
    vector <int> used(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        dusmani.push_back({x, y});
    }

    rec(1, n, v, used, dusmani);

    return 0;
}