{"id":34290,"date":"2024-11-01T09:26:26","date_gmt":"2024-11-01T09:26:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34290"},"modified":"2024-11-01T10:57:50","modified_gmt":"2024-11-01T10:57:50","slug":"c-coding-test-course-finding-the-critical-path-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34290\/","title":{"rendered":"C++ Coding Test Course, Finding the Critical Path"},"content":{"rendered":"

<\/p>\n

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.<\/p>\n

Problem Definition<\/h2>\n

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.<\/p>\n

Problem Description<\/h2>\n

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

\nInput:\nn, m\nt[0], t[1], ..., t[n-1]\nEdges: (u1, v1), (u2, v2), ..., (um, vm)\nOutput:\nMaximum task time\n<\/pre>\n
Example Input<\/h2>\n
\n5 6\n2 3 1 5 4\n0 1\n0 2\n1 3\n2 3\n2 4\n3 4\n<\/pre>\n
Example Output<\/h2>\n
\n10\n<\/pre>\n
Problem-Solving Strategy<\/h2>\n
1. Graph Representation<\/h3>\n
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.<\/p>\n
2. Finding the Longest Path<\/h3>\n
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.<\/p>\n
3. Utilizing Dynamic Programming (DP)<\/h3>\n
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.<\/p>\n
C++ Code Implementation<\/h2>\n
\n#include \n#include \n#include \nusing namespace std;\n\nvector timeTaken; \/\/ Task time for each vertex\nvector> graph; \/\/ Graph adjacency list\nvector dp; \/\/ DP array\n\nint dfs(int node) {\n    if (dp[node] != -1) return dp[node];\n    int maxTime = 0;\n    for (int next : graph[node]) {\n        maxTime = max(maxTime, dfs(next));\n    }\n    dp[node] = maxTime + timeTaken[node];\n    return dp[node];\n}\n\nint main() {\n    int n, m;\n    cin >> n >> m;\n    \n    timeTaken.resize(n);\n    graph.resize(n);\n    dp.assign(n, -1);\n    \n    for (int i = 0; i < n; i++) {\n        cin >> timeTaken[i];\n    }\n    \n    for (int i = 0; i < m; i++) {\n        int u, v;\n        cin >> u >> v;\n        graph[u].push_back(v);\n    }\n\n    int result = 0;\n    for (int i = 0; i < n; i++) {\n        result = max(result, dfs(i));\n    }\n\n    cout << result << endl;\n    return 0;\n}\n<\/pre>\n
Code Explanation<\/h2>\n
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:<\/p>\n