图上的深度优先搜索算法中的内存泄漏

Question

我在Coursera上做一门课程，他们要求实现DFS以查看图的两个顶点是否连接。我想出了代码，它在我的笔记本电脑上给出了正确的输出，但它在他们的分级机上给出了不正确的输出。在这个问题上，我已经打破了几天的头脑，完全不知道我哪里出了问题。代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Graph
{
public:
    vector<int> adj; //adjacency list
    void add(int a)
    {
        adj.push_back(a);
    }
    void DFS(bool visited[],int n,Graph G[],int v)
    {
        for(int i=0;i<G[v].adj.size();i++)
        {
            int vert=G[v].adj[i];
            if(visited[vert]==false)
            {
                visited[vert]=true;
                DFS(visited,n,G,vert);
            } 
        }
    }
};
int main()
{
    int n,m;
    cin>>n>>m;//No. of vertices,number of edges
    bool visited[n];
    for(int i=0;i<n;i++)
        visited[n]=false;
    Graph G[n];
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;  //The vertices joined by two edges
        G[u-1].add(v-1);
        G[v-1].add(u-1);
    }
    int k,l;
    cin>>k>>l; //The vertices to be checked if they are connected
    G[k-1].DFS(visited,n,G,k-1);
    if(visited[l-1]==true)
        cout<<1;
    else
        cout<<0;
}

平地机输出：

Failed case #2/16: (Wrong answer)
Input:
4 2
1 2
3 2
1 4
Your output: 
1
Correct output:
0
(Time used: 0.00/1.00, memory used: 7839744/536870912.)

如果我在笔记本电脑上运行上述情况，它会给出 0 的输出，即预期的答案。我在论坛上问了这个问题，他们说有一些我无法识别的内存泄漏。请帮忙。

Answer 1

如果你正在编写一个Graph类，那么你实际上应该将所有功能封装在该类中。您不应该压倒main功能。它使您的代码变得复杂。另外，在函数调用的情况下，您不必传递很多东西。避免使用 using namespace std;，因为它会导致命名空间冲突。为避免写入std::cout或std::cin，请考虑using std::cout和using std::cin。我重构了您的代码，现在它给出了正确的输出：

#include <iostream>
#include <cstring>
#include <vector>
using std::cout;
using std::cin;
class Graph
{
public:
    static constexpr int MAXN = 100; 
    std::vector <int> adj[MAXN + 1]; //adjacency list
    int visited[Graph::MAXN + 1]; // for 1 based indexing
    Graph(){
        for(int i = 0 ; i <= MAXN ; ++i) adj[i].clear();
        memset(visited, 0, sizeof(visited));
    }
    void addEdge(bool isDirected, int u, int v)
    {
        adj[u].push_back(v);
        if(!isDirected) adj[v].push_back(u);
    }
    void takeInput(bool isDirected, int nodes, int edges){
        for(int i = 0 ; i < edges ; i++){
            int u,v; cin >> u >> v; 
            addEdge(isDirected, u, v);
        }
    }
    void DFS(int source)
    {
        visited[source] = 1;
        for(int i = 0 ; i < adj[source].size() ; ++i){
            int adjNode = adj[source][i];
            if(visited[adjNode] == 0){
                DFS(adjNode);
            } 
        }
    }
    bool isConnected(int source, int destination){
        DFS(source - 1);
        return visited[destination - 1];
    }
};
int main()
{
    int nodes, edges;
    cin >> nodes >> edges;//No. of vertices,number of edges
    Graph g;
    g.takeInput(false, nodes, edges);
    int source, destination;
    cin >> source >> destination; //The vertices to be checked if they are connected
    cout << g.isConnected(source, destination) << 'n';
    return 0;
}