有没有办法让骑士们坐在圆桌旁，让每个骑士都坐在他的朋友旁边？

Question

我在进行一些编码挑战时偶然发现了这个问题：

圆桌位于一个巨大的大厅里，周围有N张椅子。每个骑士都想坐在他的朋友附近，否则他拒绝坐。
第一行给出一个整数 n，其中 n 是圆桌骑士的数量 ( 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.
输出
如果骑士们可以围坐在圆桌旁，则显示“是”，否则显示“否”。

根据我的理解，我们得到了一个基本上是无向图的邻接矩阵，其中节点是骑士，边代表友谊关系。现在我的想法是在图中搜索长度为 N 的循环，或哈密顿循环。如果是这样，则输出 YES，否则输出 NO。

我的代码确实适用于所提供的基本示例，但不知何故，它在 N 足够大的某个测试中失败了。 （注意是错误答案，不是Time Limit错误）

这是我的代码：

#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;
}

我是否遗漏了一些完全明显的东西，这些东西会使我的代码在输入更大的情况下失败。还是我遗漏了任何需要处理的特殊情况？

如有任何提示，我将不胜感激。预先感谢！

输入示例：

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

输出示例：

是

Answer 1

一般来说，最好为您的图表使用标准库。如果您每次都从头开始编写顶点和边数据结构，您将失去效率并花费一半的时间来调试图结构，而不是您的算法。

一般来说，我避免使用递归函数，因为它们不能扩展到大图。在这种情况下，递归函数对于跟踪路径长度非常方便，所以让我们继续使用它。最小化递归函数的参数非常重要，以免耗尽堆栈内存。因此，使递归函数成为类方法，并将尽可能多的参数移动到类属性中。

像这样：

#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;
}