1
$\begingroup$

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't find any problem with my logic. Maybe I made some implementation mistake during the contest (I'm not sure). But now I have my solution and I don't know if it's correct or not. I have tried it on multiple graphs and it gives correct answer on all of them. But yes a single case is enough to prove an algorithm wrong. So below I provide the details. Please help me validate the solution.

Problem Given an un-directed graph (can be disconnected) with N nodes and E edges. The stress level of the path is defined as the maximum weight of an edge present on this path. Given a source U and destination V you need to tell the minimum stress level from node U to node V. If you cannot reach V from U, return -1.

My Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

int minStressLevel(vector<vector<pair<int, int> > > &adj, set<pair<int, int> > 
&visited, int src, int dst) {
    if(src == dst) return 0;

        int ans = INT_MAX;
        for(auto to: adj[dst]) {
        int v = to.first;
        int w = to.second;

        if(!visited.count({dst, v})) {
            visited.insert({dst, v});
            visited.insert({v, dst});
            ans = min(ans, max(minStressLevel(adj, visited, src, v), w));
        }
    }

    return ans;
}

int32_t main() {
    int t;
    cin >> t;

    for(int d = 0; d < t; d++) {
        int n, e;
        cin >> n >> e;

        vector<vector<pair<int, int> > > adj(n + 1);

        for(int i = 0; i < e; i++) {
            int u, v, w;
            cin >> u >> v >> w;

            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector<int> dp(n + 1, INT_MAX);
        set<pair<int, int> > visited;

        int source, destination;
        cin >> source >> destination;

        int ans = minStressLevel(adj, visited, source, destination);
        cout << "Case #" << d << ": ";
        if(ans == INT_MAX) cout << -1 << endl;
        else cout << ans << endl;
    }
}

Explanation The solution is based on this recurrence: minStressLevel(V) = min{max(minStressLevel(K), edge_weight(K, V))} over all neighbours K of V.

I keep a set of pairs to keep track of what edges have been visited so that I don't get into infinite loops. This is different than a simple Breadth First Search where we stop once we discover a vertex and do not visit it again.

Time Complexity I think time complexity is O(E), where E is the number of edges. Constraints N <= 1e5 E <= 1e5 edge_weight <= 1e9

Improve this question
$\endgroup$
1
  • $\begingroup$ Checking your code is off-topic here. Coding questions are off-topic here, and not everyone knows C++, so we request people to use concise pseudocode rather than providing code. $\endgroup$
    – D.W. ♦
    Oct 11, 2021 at 4:45

1 Answer 1

Reset to default
1
$\begingroup$

I don't think your algorithm is correct, but keep in mind that I haven't read your code carefully; consider replacing the code with pseudocode.

One solution that could work in $O(m \log m)$ time is to binary search for the stress level and do BFS on only edges with lower weight.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes you are right, the algorithm is incorrect, I was working on it and found the same. Infact the output of algo depends on order of edges. By the way, In you answer do I have to check for connectivity after binary search's check function ? Also do you think it can be dijkstra ? $\endgroup$
    – KnownUnknown
    Oct 10, 2021 at 16:29
  • $\begingroup$ I am saying dijkstra because consider the recurrecnce minStressLevel(V) = min{max(minStressLevel(K), edge_weight(K, V))} over all neighbours K of V. It is very similar to shortest path recurrence dist[v] = min(dist[u] + edge_weight(u,v)) $\endgroup$
    – KnownUnknown
    Oct 10, 2021 at 16:42
  • $\begingroup$ You can use dijkstra if you want, but bfs and in fact DFS too will work. Since you only traverse the weights smaller than a threshold, you only care if u and v are in the same component. $\endgroup$
    – Pål GD
    Oct 10, 2021 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.