C++ bfs solution with explanation


  • 0
    Q
    /*
    // Employee info
    class Employee {
    public:
        // It's the unique ID of each node.
        // unique id of this employee
        int id;
        // the importance value of this employee
        int importance;
        // the id of direct subordinates
        vector<int> subordinates;
    };
    */
    class Solution {
    public:
        int getImportance(vector<Employee*> employees, int id) {
            map<int,vector<int>> graph;
            map<int,int> weight;
            for(auto it:employees){
                graph[it->id] = it->subordinates;
                weight[it->id] = it->importance;
            }
            queue<int> q;
            q.push(id);
            int res = weight[id];
            while(!q.empty()){
                int idx = q.front();
                q.pop();
                for(auto it:graph[idx]){
                    res += weight[it];
                    q.push(it);
                }
            }
            return res;
        }
    };
    

    tips: since this is a directed graph, we do not need to maintain a visited array to mark whether the node has been visited or not


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.