Longest Paths

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.

 

Input 

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.

 

Output 

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.

 

Sample Input 

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

 

Sample Output 

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.Collections;

using System.Linq;

using System.Text;

using System.Text.RegularExpressions;

using System.IO;

 

namespace ConsoleApplication1

{

    class Program

    {

        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];

                    flag++;

                }

                else if (flag == 1)

                {

                    startNode = int.Parse(str) – 1;

                    flag++;

                }

                else

                {

                    Regex reg = new Regex(" ");

                    string[] strArray = reg.Split(str);

                    connectionMatrix[int.Parse(strArray[0]) – 1, int.Parse(strArray[1]) – 1] = 1;

                }

            }

            sr.Close();

            RecursiveTraversal(connectionMatrix, startNode);

            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)

                {

                    tempLength++;

                    if (longestPathLength <= tempLength)

                    {

                        if (longestPathLength < tempLength)

                        {

                            longestPathLength = tempLength;

                            endNode = i;

                        }

                        else

                        {

                            if (endNode > i)

                                endNode = i;

                        }

                    }

                    RecursiveTraversal(connectionMatrix, i);

                }

            }

            tempLength–;

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s