Your goal is to develop a program that computes the length of the longest path that can be constructed in a given graph from a given starting point. You can assume that the graph has no cycles (there is no path from any node to itself). In the same line of reasoning, nodes are not considered directly connected to themselves.
The input consists of a number of cases. The first line on each case contains a positive number n (1<n<=100) that specifies the number of nodes in the graph. A value of n = 0 indicates the end of the input. After this, a second number s is provided, indicating the starting point (1<=s<=n). Then, you are given a list of pairs of places p and q, one pair per line, with the places on each line separated by white-space. The pair “p q” indicates that q can be visited after p. A pair of zeros (“0 0”) indicates the end of the case.
For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.
Print a new line after each test case.
Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
public static int longestPathLength = 0;
public static int tempLength = 0;
public static int endNode = 0;
static void Main(string args)
StreamReader sr = new StreamReader(@"D:\input.txt");
int numberOfNodes = 0;
int[,] connectionMatrix = new int[numberOfNodes, numberOfNodes];
int startNode = 0;
string str = null;
int flag = 0;
while ((str = sr.ReadLine()) != null)
if (flag == 0)
numberOfNodes = int.Parse(str);
connectionMatrix = new int[numberOfNodes, numberOfNodes];
else if (flag == 1)
startNode = int.Parse(str) – 1;
Regex reg = new Regex(" ");
string strArray = reg.Split(str);
connectionMatrix[int.Parse(strArray) – 1, int.Parse(strArray) – 1] = 1;
Console.WriteLine("The longest path from " + (startNode + 1)
+ " has length " + longestPathLength
+ ", finishing at " + (endNode + 1)
public static void RecursiveTraversal(int[,] connectionMatrix, int startNode)
for (int i = 0; i < connectionMatrix.GetLength(1); i++)
if (connectionMatrix[startNode, i] == 1)
if (longestPathLength <= tempLength)
if (longestPathLength < tempLength)
longestPathLength = tempLength;
endNode = i;
if (endNode > i)
endNode = i;