C++ Coding Test Course, Finding the Critical Path

Hello. In this lecture, we will discuss “Finding the Critical Path,” which is one of the algorithm problems frequently asked in C++ coding tests. This problem helps in understanding important concepts related to graph theory.

Problem Definition

In the given directed graph, each vertex has a specific time to perform a task. The critical path refers to the total task time of the longest path among all paths that visit all vertices, from the starting vertex to the destination vertex.

Problem Description

Given the number of vertices n and the number of edges m, the task time for each vertex i is given as t[i]. The problem is to find the maximum task time of a path that satisfies the following conditions.

Input:
n, m
t[0], t[1], ..., t[n-1]
Edges: (u1, v1), (u2, v2), ..., (um, vm)
Output:
Maximum task time

Example Input

5 6
2 3 1 5 4
0 1
0 2
1 3
2 3
2 4
3 4

Example Output

10

Problem-Solving Strategy

1. Graph Representation

First, we construct the graph in the form of an adjacency list based on the given information. This allows us to easily manage movements to connected vertices from each vertex.

2. Finding the Longest Path

We can use DFS (Depth-First Search) or the properties of a DAG (Directed Acyclic Graph) to find the longest path. As we visit each vertex, we keep track of the maximum task time of the longest path.

3. Utilizing Dynamic Programming (DP)

In particular, the problem of finding the critical path can be efficiently solved using dynamic programming. We accumulate and record the maximum of all reachable paths for each vertex.

C++ Code Implementation

#include 
#include 
#include 
using namespace std;

vector timeTaken; // Task time for each vertex
vector> graph; // Graph adjacency list
vector dp; // DP array

int dfs(int node) {
    if (dp[node] != -1) return dp[node];
    int maxTime = 0;
    for (int next : graph[node]) {
        maxTime = max(maxTime, dfs(next));
    }
    dp[node] = maxTime + timeTaken[node];
    return dp[node];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    timeTaken.resize(n);
    graph.resize(n);
    dp.assign(n, -1);
    
    for (int i = 0; i < n; i++) {
        cin >> timeTaken[i];
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    int result = 0;
    for (int i = 0; i < n; i++) {
        result = max(result, dfs(i));
    }

    cout << result << endl;
    return 0;
}

Code Explanation

The above code explores the graph in a DFS manner to calculate the maximum task time of the critical path. The main elements are as follows:

• Graph Creation: The graph is constructed in the form of an adjacency list through the input edges.
• DFS Function: Starting from each vertex, it recursively explores the connected vertices and computes the time of the longest path.
• DP Array: A DP array is utilized to apply memoization techniques to avoid revisiting the same vertex multiple times.

Time Complexity

The time complexity of this algorithm is O(n + m). Here, n is the number of vertices, and m is the number of edges. In the worst case, since all vertices must be visited once, this level of complexity is generally efficient.

Conclusion

In this lecture, we learned how to solve the critical path problem using C++. Through the concepts of graph theory, dynamic programming, and DFS, we can address this type of problem. I hope you will practice various algorithm problems to improve your programming skills further.