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 (
)
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 (
). 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 ``
" 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.
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0
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.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication6
{
class Program
{
static int maxcount = 0;//Variable to store the length of the longest path.
static int final = 0;//Variable to store the final node.
static bool visit = false;//Variable to check if the else part has been visited at least once.
static void Main(string[] args)
{
int num = int.Parse(Console.ReadLine());
int start = int.Parse(Console.ReadLine());
int initial = start;
int[,] arr = new int[num, num];
int[] trav = new int[num];
int num1, num2;
//Converting the input into the corresponding incidence matrix.
while((num1= int.Parse(Console.ReadLine()))!=0)
{
num2 = int.Parse(Console.ReadLine());
arr[num1 - 1, num2 - 1] = 1;
}
pathfinder(arr, start - 1, 0, trav);
Console.WriteLine("The longest path from " + initial + " has length " + maxcount + " finishing at " + final);
}
static void pathfinder(int[,] arr, int row, int count, int[]trav)
{
//Base case: The node from which no link to other nodes is found.
if (trav[row] == 1 && arr[row, arr.GetLength(0) - 1] == 0 && visit == true)
{
if (maxcount < count)
{
maxcount = count;
final = row + 1;
}
return;
}
else
{
visit = true;
for (int i = 0; i < arr.GetLength(0); i++)
{
trav[row] = 1;
if (arr[row, i] == 1)
{
count++;
//Sending the control to that row, the link of which is found here.
pathfinder(arr, i, count, trav);
trav[row] = 0;
count--;
}
}
}
if (maxcount < count)
{
maxcount = count;
final = row + 1;
}
}
}
}
