I was trying to solve leetcode323. My code and my way to solve the problem was basically identical to the official answer. The only difference was that I was using vector<vector> while the official answer used vector [] to keep the neighbors of each node. When I used vector [], the system accepted my answer. Is there any advantages of using vector [] over using vector<vector>? I put my code and the official solution code below. Thank you so much in advance.

My code:

class Solution {
    public :
    void explore(vector<bool> & visited,vector<int> nei[],int cur){
        visited[cur]=true;
        for(int i=0;i<nei[cur].size();i  ){
            if(!visited[nei[cur][i]]){
                explore(visited,nei,nei[cur][i]);
            }
        }
    }
    
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<bool> visited(n);
       vector<vector<int>> neighbors(n);
        int count=0;
        for(int i=0;i<edges.size();i  ){
            neighbors[edges[i][0]].push_back(edges[i][1]);
             neighbors[edges[i][1]].push_back(edges[i][0]);
        }
        for(int j=0;j<n;j  ){
            if(!visited[j]){
                count  ;
                explore(visited,neighbors,j);
            }
        }
        return count;

    }
};

Official solution

class Solution { 
public: void dfs(vector<int> adjList[], vector<int> &visited, int src) { 
visited[src] = 1;    

for (int i = 0; i < adjList[src].size(); i  ) {
        if (visited[adjList[src][i]] == 0) {
            dfs(adjList, visited, adjList[src][i]);
        }
    }
}

int countComponents(int n, vector<vector<int>>& edges) {
    if (n == 0) return 0;
  
    int components = 0;
    vector<int> visited(n, 0);
    vector<int> adjList[n];

    for (int i = 0; i < edges.size(); i  ) {
        adjList[edges[i][0]].push_back(edges[i][1]);
        adjList[edges[i][1]].push_back(edges[i][0]);
    }
    
    for (int i = 0; i < n; i  ) {
        if (visited[i] == 0) {
            components  ;
            dfs(adjList, visited, i);
        }
    }
    return components;
}
};

CodePudding user response：

I'm not sure, but I think the main problem of your solution is std::vector<bool> which is special case of std::vector.

In the '90s memory size was a problem. So to save memory std::vector<bool> is a specialization of std::vector template and single bits are used to store bool value. This compacts memory, but comes with performance penalty. Now this has to remain forever to be compatible with already existing code.

I would recommend you to replace std::vector<bool> with std::vector<char> and do not change anything else. Let implicit conversion between bool and char do the magic.

Second candidate is missing reserve for adjList[i] as mentioned in other answer, but "official" solution doesn't do that either.

Here I refactor your code.

CodePudding user response：

The only difference was that I was using vector<vector<int>>

There are several differences:

• Official uses (non standard C ) VLA, whereas you use compliant vector<vector<int>>.

  I would say that VLA "allocation" (similar to alloca) is faster than real allocation from std::vector (new[]).
  From your test, assuming timing is done correctly, VLA seems to have a real impact.

• Official use vector<int> whereas you use std::vector<bool>

  With specialization, vector<bool> is more compact than std::vector<int /*or char*/> but would require a little more work to set/retrieve individual value.

• You have some different names.

  Naming difference should not impact runtime.
  In some circonstance, very long difference and template usage might impact compilation time. But it should not be the case here.

• Order of parameters of dfs/explore are different.

  It might probably allow micro optimization in some cases, but swapping the 2 vectors doesn't seem to be relevant here.

Is there any advantages of using vector [] over using vector<vector>?

VLA is non standard C , that is a big disadvantage.
Stack is generally more limited than heap, so size of "array" is more limited.

Its advantage seems to be a faster allocation.

The usage speed should be similar though.