jeudi 25 juin 2020

Heaviest path from root to leaf in an undirected weighted tree

I am given an bidirectional weighted tree with n nodes (root at 1). I am supposed to implement an algorithm which can find the total weight of the heaviest path from root to leaf.

Here is what I have implemented (not working for hidden test cases) :

void dfs(std::vector<std::map<int, int>> &adj, std::vector<bool> &visited, int &max_len, int src = 1, int prev_len = 0) {
    visited[src] = true;
    int curr_len = 0;
    for (auto &i : adj[src]) {
        if (not visited[i.first]) {
            curr_len = prev_len + i.second;
            dfs(adj, visited, max_len, i.first, curr_len);
        }
        max_len  = max(max_len, curr_len);
        curr_len = 0;
    }
}

int longestPath(std::vector<std::map<int, int>> &adj) {
    int               max_len = 0;
    std::vector<bool> visited(adj.size());
    dfs(adj, visited, max_len);
    return max_len;
}

Tree is constructed using the following method:

void addEdge(std::vector<std::map<int, int>> &adj, int u, int v, int w = 0) {
    adj[u][v] = w;
    adj[v][u] = w;
}

Driver function:

signed main() {
    int n, u, v, w;
    std::cin >> n;
    std::vector<std::map<int, int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        std::cin >> u >> v >> w;
        addEdge(adj, u, v, w);
    }
    std::cout << longestPath(adj);
    return 0;
}

What am I doing wrong here?

Aucun commentaire:

Enregistrer un commentaire