Is there a way for the knights to be seated at a round table so that each knight sits near his friends?

Question

I stumbled upon this problem while doing some coding challenges:

The Round Table is located in a huge hall, rounded by N chairs. Each knight wants to sit near his friends, otherwise he refuses to sit.
In the first line is given an integer number n, where n is the number of the Knights of the Round Table ( 3<=n<=100 ). The knights are numbered from 1 to n. Each of the following n lines contains a sequence of n values 0 or 1, separated by a space. The ith sequence shows the friendship relations of the ith knight. The jth value determines if the ith knight is a friend of the jth knight. They are friends if the value is 1, and not friends if the value is 0. Since friendship is reciprocal, if I is a friend of j, j is also friend of i.
Output
If the knights can be sit around the round table, show ‘YES’, otherwise show ‘NO’.

From what I understood, we are given an adjacency matrix of what is basically a undirected graph, where the nodes are the knights and the edges represent the friendship relations. Now my idea was to search for a cycle of length N in the graph, or a Hamiltonian Cycle. If that is the case, output YES, otherwise NO.

My code does work for the basic examples that are provided, but somehow it is failing at a certain test where N gets large enough. (Note that it is a wrong answer, not Time Limit error)

This is my code:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void dfs_search(vector<vector<int> > &matrix, vector<bool> &visited, int node, int parent, int n, int path, bool &found){
    if(found)
        return;
    else if(visited[node] && node == parent && path == n){
        found = 1;
        return;
    }
    else if(visited[node])
        return;
    else{
        visited[node] = 1;
        path++; 
        //cout<<node<<" "<<path<<endl;
        
        for(int i=0; i < n; i++){
            if(matrix[node][i] == 1){
                dfs_search(matrix, visited, i, parent, n, path, found);
            }
        }

        visited[node] = 0;
        path--;
    }

}
int main(){

    int n;

    cin >> n;

    bool found = 0;

    vector<vector<int> > matrix(n, vector<int>(n));
    vector<bool> visited(n, 0);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin>>matrix[i][j];
    }

    for(int i=0; i<n; i++){
        dfs_search(matrix, visited, i, i, n, 0, found);
        if(found){
            break;
        }
    }
    
    if(found)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}

Am I missing something completely obvious that would make my code fail with bigger input. Or am I missing any special case that needs to be handled?

I would appreciate any tip. Thanks in advance!

Example Input:

5
0 1 1 0 1
1 0 0 1 1
1 0 0 1 1
0 1 1 0 1
1 1 1 1 0

Example Output:

YES

Answer 1

In general, it is best to use a standard library for your graph. If you code a vertex and edge data structure from scratch every time, you will miss out on efficiencies and spend half your time debugging the graph structure, rather then your algorithm.

In general, I avoid using recursive functions, since they are not scalable to large graphs. In this case a recursive function is very convenient for keeping track of the path length, so let's stick with that. It is important to minimize the parameters to the recursive function, so as not to run out of stack memory. So make the recursive function a class method and move as many parameters as possible to class attributes.

Like this:

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include "cGraph.h" // https://github.com/JamesBremner/PathFinder

class cSeatFinder
{

public:
    void generateExample1();

    void arrangeSeating();

private:

    raven::graph::cGraph g;

    std::vector<bool> visited;

/**
 * @brief Determine if the there is a cycle that includes every node
 * 
 * @param node current node being explored
 * @param pathlength length of path to current node from start
 * 
 * Recursive.  Assumes starting node has id 0
 * 
 * If full cycle found, throws an exception std::runtime_error("found seating");
 * If not found, returns to caller
 */
    void dfs_full_cycle(
        int node,
        int pathlength);
};

void cSeatFinder::generateExample1()
{
    g.add(0, 1);
    g.add(0, 2);
    g.add(0, 4);
    g.add(1, 3);
    g.add(1, 4);
    g.add(2, 3);
    g.add(2, 4);
    g.add(3, 4);
}

void cSeatFinder::dfs_full_cycle(
    int node,
    int pathlength)
{

    // check if we have returned to the start
    if ( node == 0 ) {
        
        // check if we have visited every node
        if( pathlength == g.vertexCount()) {

            throw std::runtime_error("found seating");
        }
    }

    if (visited[node])
        return;

    visited[node] = 1;
    pathlength++;

    for (int vi : g.adjacentOut(node))
        dfs_full_cycle( vi, pathlength );

    visited[node] = 0;
    pathlength--;
}
void cSeatFinder::arrangeSeating()
{
    visited.resize(g.vertexCount(), false);
    try
    {
        dfs_full_cycle( 0, 0 );
    }
    catch (std::runtime_error &e)
    {
        if (e.what() == std::string("found seating"))
        {
            std::cout << "YES\n";
            return;
        }
    }

    std::cout << "NO\n";
}

main()
{
    cSeatFinder theSeatFinder;

    theSeatFinder.generateExample1();

    theSeatFinder.arrangeSeating();

    return 2;
}