C# Coding Test Course, Finding the Critical Path

Problem Description

This is a problem of finding the critical path in a given directed graph. The critical path is represented by nodes and edges in the graph and is about solving for the longest path. The given graph consists of n number of nodes and m number of edges.

Input Format

  • The first line contains integers n and m.
  • The next m lines each contain a pair of integers u and v. This represents an edge from node u to node v.

Output Format

Output the length of the longest path.

Example Input

    6 7
    1 2
    1 3
    2 4
    3 4
    4 5
    5 6
    3 6

Example Output

4

Problem Solving Process

To solve this problem, we can use the following method.

Step 1: Graph Representation

Represent the given directed graph in the form of an Adjacency List. This allows us to easily check which nodes can be reached from each node.

Step 2: Topological Sorting

To find the longest path, we need to visit all the nodes in the graph once. We use topological sorting for this purpose. Through topological sorting, all nodes can be visited in order.

Step 3: Longest Path Calculation

After completing the topological sort, we calculate the longest path from the starting node to each node. At this time, we use an array to store the values of the longest path.

Step 4: Code Implementation

Below is an example of code implementation to find the critical path using C#:


using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 6; // Number of nodes
        int m = 7; // Number of edges
        List[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List();
        }

        // Input edge information
        graph[1].Add(2);
        graph[1].Add(3);
        graph[2].Add(4);
        graph[3].Add(4);
        graph[4].Add(5);
        graph[5].Add(6);
        graph[3].Add(6);
        
        // Adjacency matrix for topological sorting
        int[] inDegree = new int[n + 1];
        foreach (var edges in graph) {
            foreach (var v in edges) {
                inDegree[v]++;
            }
        }

        // Queue for topological sorting
        Queue queue = new Queue();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        // Longest path calculation
        int[] longest = new int[n + 1];
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            foreach (var v in graph[u]) {
                longest[v] = Math.Max(longest[v], longest[u] + 1);
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.Enqueue(v);
                }
            }
        }

        // Output result
        int maxPath = 0;
        for (int i = 1; i <= n; i++) {
            maxPath = Math.Max(maxPath, longest[i]);
        }
        Console.WriteLine(maxPath);
    }
}

Code Explanation

The code above works as follows:

  1. It represents the graph using the List data structure.
  2. Calculates the in-degree of each node for all edges.
  3. Adds nodes with in-degree of 0 to the queue for topological sorting.
  4. Updates the longest path for each node in the order of the topological sort.
  5. Finally, it outputs the length of the longest path.

Conclusion

The problem of finding the critical path can be efficiently solved through topological sorting and longest path calculation. This method can be applied to various path optimization problems, making basic understanding and practice essential.

I hope this article helps in preparing for C# coding tests! If you have any additional questions or need further explanations, please leave a comment.

Author: [Your Name]