Time Needed to Inform All Employees Solutions in C++

// Source : https://leetcode.com/problems/time-needed-to-inform-all-employees/
// Author : Shreya Vanga
// Date   : 2020-10-02







class Solution {
public:
    vector<int>visited;
    long long int dfs(vector<vector<int>>& adj, vector<int>& informTime, int src, int n)
    {
        long long int count = 0;
        for(int i=0;i<adj[src].size();i++)
        {
            count = max(count,dfs(adj, informTime, adj[src][i], n));
        }
        return (informTime[src]+count);
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>>adj(n);
        for(int i=0;i<manager.size();i++)
        {
            if(manager[i] != -1)
                adj[manager[i]].push_back(i);
        }
        long long int time;
        visited.resize(n,0);
        visited[headID] = 1;
        time= dfs(adj, informTime, headID, n);
        return time;
    }
};

/// Source : https://leetcode.com/problems/time-needed-to-inform-all-employees/
/// Author : liuyubobobo
/// Time   : 2020-03-07

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// DFS
/// Time Complexity: O(V + E)
/// Space Complexity: O(V + E)
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

        vector<set<int>> g(n, set<int>());
        for(int i = 0; i < n; i ++)
            if(i != headID) g[i].insert(manager[i]), g[manager[i]].insert(i);

        vector<bool> visited(n, false);
        return dfs(g, n, headID, visited, informTime);
    }

private:
    int dfs(const vector<set<int>>& g, int n, int node,
            vector<bool>& visited, const vector<int>& informTime){

        visited[node] = true;
        int res = 0;
        for(int next: g[node])
            if(!visited[next])
                res = max(res, dfs(g, n, next, visited, informTime));
        return res + informTime[node];
    }
};


int main() {

    vector<int> manager1 = {-1};
    vector<int> informTime1 = {0};
    cout << Solution().numOfMinutes(1, 0, manager1, informTime1) << endl;
    // 0

    vector<int> manager2 = {2,2,-1,2,2,2};
    vector<int> informTime2 = {0,0,1,0,0,0};
    cout << Solution().numOfMinutes(6, 2, manager2, informTime2) << endl;
    // 1

    vector<int> manager3 = {1,2,3,4,5,6,-1};
    vector<int> informTime3 = {0,6,5,4,3,2,1};
    cout << Solution().numOfMinutes(7, 6, manager3, informTime3) << endl;
    // 21

    return 0;
}