Count the number of nodes in a Graph whose sum of neighbors is at most K

Approach

Our idea for solving the problem is to traverse the graph using DFS Algorithm and count the sum of the neighbours' values. We compare and ensure that the sum doesn't exceed K and increase the answer count depending on it being less than or equal to K.

Our algorithm below follows the following steps:

1. Initialize and build the input graph.
2. Use DFS to visit every node and record the visited nodes in the unordered_set.
3. Return if the node was previously visited.
4. Calculate the sum of values of the neighbouring nodes and recurse through the whole graph, as in DFS.
5. If the sum is less than equal to K, increment the answer by one and return it.

Code in C++

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


/*
    uncomment if you need to use long long for testing instead of int
*/
// #define int long long


class Node{
    public:
    vector<Node *> neigh;
    int val;
    Node(int x){
        val = x;
    }
    void insert(Node *x){
        neigh.push_back(x);
    }
};


int countNodesWithNeighborSumNotMoreThanK(Node* start, unordered_set<Node *>& vis, int K){
    
    // if node already visited, return back
    if(vis.find(start) != vis.end()) return 0;
    
    vis.insert(start);
    
    int sum = 0, ans = 0;
    
    for(int i = 0; i < start->neigh.size(); i++){
        ans += countNodesWithNeighborSumNotMoreThanK(start->neigh[i], vis, K);
        sum += start->neigh[i]->val;
    }


    if(sum <= K) ans += 1;
    
    return ans;
}


int32_t main(){
    // edit the data and check the output for various graphs
    // list of node values
    vector<int> a = {1, 2, 3, 4, 5};
    vector<Node *> v;
    for(int x: a){
        v.push_back(new Node(x));
    }
    // adjacency list for neighbors
    vector<vector<int>> neighbors = {
        {1, 3, 4},
        {0},
        {3, 4},
        {0, 2},
        {0, 2}
    };
    // K value for the problem
    int K = 4;
    for(int i = 0; i < neighbors.size(); i++){
        for(int j: neighbors[i]){
            v[i]->insert(v[j]);
        }
    }
    unordered_set<Node *> vis;
    cout << countNodesWithNeighborSumNotMoreThanK(v[0], vis, K);
}

Output

3

Time Complexity

Time Complexity for the given algorithm is O(V + E), here V are the number of nodes, and E are the edges in the graph. This time complexity is identical to DFS as that's essentially all that's happening in the code.

Space Complexity

Extra space O(V + h) other than the input is required by the algorithm, O(V) space is required by unordered_set for storing the visited positions, here h is the stack depth at max. h can at maximum be V (number of nodes), so the worst-case space complexity of the algorithm is O(V). This happens when we have a chain-like graph, as shown below. If 1 is the start node, then the stack depth at max will be V.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

1. Why did we prefer to use DFS, and can we use BFS instead?

One can easily do the same problem using BFS, and I recommend you to try the problem using BFS and observe the difference. Observe the difference in memory consumed for different graphs with the same algorithms. This observation will give you a better idea of which algorithm performs better in which type of graph.

2. Difference between unordered_set and set in C++ STL?

The set data structure is usually implemented using a red-black tree (read more about it here). The unordered_set, however, is implemented using a hash table and hence offers an average O(1) retrieval and insertion. In contrast, set data structure takes O(log(n)) for retrieving and inserting an element.

3. Is unordered_set always better than set?

No, the unordered_set will usually work well with random data and give O(1) retrieval and insertion on average. Still, in case of excessive collisions (which can be the case for some specific inputs, depending on the hash function), our retrieval and insertion may become O(N).

Key Takeaways

The article helps us understand applications of graph traversals algorithms such as DFS, understanding and approaching related problems and implementing them. Go through the basics of graph theory here to better understand and follow the blog and read a bit about Graph Traversal Algorithms here and recursion here.

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!