Incompatible species

Go to the Jutge statement of the problem

Consider n different species. Some may be incompatible, in the sense that they must be kept separated. For example, if the species were human, lion, gorilla, buffalo and antelope, then the list of incompatibilities might be: we cannot put a human next to a lion, nor a human next to a buffalo, nor a lion next to a buffalo, nor a lion next to a antelope.

Write a program that reads the incompatibilities between species, and writes all the ways to put in a row an individual of every species, so that two incompatible species are never one beside the other.

Input: Input begins with a number n between 1 and 52, followed by n letters, each identifying a different species. Then comes a number m, followed by m different pairs of letters, each indicating an incompatibility between two of the n given species.

Output: Print all the ways of placing n individuals in a row, one of each species, so that incompatible species are not together.

You can print the solutions to this exercise in any order.

Hint

The incompatibilities between species correspond to a graph. Since we are only interested in the edges if they are present or not (and the graph is not too big) it might be useful to store it as an adjacency matrix. Perhaps it might be useful to think as the chars associated to each vertex as a label, and the vertex as an int.

For instance as vector<vector<bool>> adj(256, VB(256,true)).

A possible C++ code to start the problem

// incompatible species
#include<iostream>
#include<vector>
#include<string>

using namespace std;
using VB = vector<bool>;
using VVB = vector<VB>;
using VC = vector<char>;

void gen(int k, string& sol, VB& mkd, const VVB& adj, const VC& i2c){
    // backtracking
}

int main(){
    int n;
    cin >> n;
    VC i2c(n);
    for (int i = 0; i < n; ++i){
        cin >> i2c[i];
    }
    int m;
    cin >> m;
    VVB adj(256, VB(256,true)); //use adj matrix
    for (int i = 0; i < m ; ++i){
        // read input
    }
    string sol(n, ' ');
    VB mkd(256, false);
    gen(0, sol, mkd, adj, i2c);
}

A possible solution

// incompatible species
#include<iostream>
#include<vector>
#include<string>

using namespace std;
using VB = vector<bool>;
using VVB = vector<VB>;
using VC = vector<char>;




void gen(int k, string& sol, VB& mkd, const VVB& adj, const VC& i2c){
    int n = sol.size();
    if (k == n) cout << sol << endl;
    else{
        for (int i = 0; i < n; ++i){
            char c = i2c[i];
            if (not mkd[c] and (k == 0 or adj[sol[k-1]][c])){
                mkd[c] = true;
                sol[k] = c;
                gen(k+1, sol, mkd, adj, i2c);
                mkd[c] = false;
            }
        }
    }

}

int main(){
    int n;
    cin >> n;
    VC i2c(n);
    for (int i = 0; i < n; ++i){
        cin >> i2c[i];
    }
    int m;
    cin >> m;
    VVB adj(256, VB(256,true)); //use adj matrix
    for (int i = 0; i < m ; ++i){
        char u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = false;
    }
    string sol(n, ' ');
    VB mkd(256, false);
    gen(0, sol, mkd, adj, i2c);
}

Other Links