-1

I was looking at code on this link:
http://codeforces.com/contest/459/submission/7495216
The code is that given a directed weighted graph and wanna find the longest path with strictly increasing edges.
Can anyone help me?

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 300005;
vector<pair<int, int> > w[MAX];
int dp[MAX], tmp[MAX];
int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, len;
        cin >> u >> v >> len;
        w[len].push_back(make_pair(u, v));
    }
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < w[i].size(); j++)
        {
            int u = w[i][j].first, v = w[i][j].second;
            tmp[v] = 0;
        }
        for (int j = 0; j < w[i].size(); j++)
        {
            int u = w[i][j].first, v = w[i][j].second;
            tmp[v] = max(tmp[v], dp[u] + 1);
        }
        for (int j = 0; j < w[i].size(); j++)
        {
            int u = w[i][j].first, v = w[i][j].second;
            dp[v] = max(dp[v], tmp[v]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}
3
  • To those voting to close: I don't think the question is too broad. Calculating the complexity of a function is pretty narrow. The close vote isn't a super-downvote. Commented Jan 27, 2016 at 18:56
  • @VincentSavard For this Q&A to become useful to anyone you would have to explain how to determine algorithmic complexity. This is too broad in my opinion. The author does not give a narrow enough issue about the general problem.
    – typ1232
    Commented Jan 27, 2016 at 19:18
  • @typ1231 this may appear boring for you,well it's not for me
    – math.
    Commented Jan 28, 2016 at 10:38

1 Answer 1

0

For each node this code iterates over all outgoing edges. So the runtime complexity is O(n*m) where n is the number of nodes and m is the number edges.

Edit: After a closer look at the data and the code, I say the complexity is O(n+m). The first and the second loop iterate over all edges, so O(m), and the third loop iterates over all nodes, so O(n).

2
  • the author of the code is saying it's O(n+m*log(m))
    – math.
    Commented Jan 28, 2016 at 10:40
  • After a closer look at the code it is O(n+m) because the second loop only iterates over all edges. I'll correct my answer but I don't see a reason for m*log(m). There is no comparing sort involved. He's using bucket sort which has a complexity of O(m). Commented Jan 28, 2016 at 19:22

Your Answer

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

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