CODEWITHSUNDEEP
c++algorithmtreedepth-first-search
Shubham
Shubham

Reputation: 2855

Finding longest path in an undirected tree

I was trying to find the longest path in an undirected tree (http://www.spoj.com/problems/PT07Z/) and made the following code.

#include <iostream>
#include <vector>

using namespace std;

vector< vector<int> > graph;
int q=0, m = -1;                                // m is for largest path and q is one of the end vertex of that path

void dfs(int i, int count, vector<bool>& v)
{
    v[i] = true;
    for(int j=0;j<graph[i].size();j++)
    {
        if(!v[graph[i][j]])
        {
            count++;                            // count is the length of the path from the starting vertex to current vertex
            dfs(graph[i][j], count, v);
        }
    }
    if(count>m)
    {
        m= count;
        q=i;
    }
    count--;                                    // decreasing count since the method return to its calling function
}


int main()
{
    int n, x, i, y;
    cin>>n;
    graph = vector< vector<int> >(n);
    vector<bool> visited(n);
    vector<bool> v(n);
    for(i=0;i<n-1;i++)
    {
        cin>>x>>y;
        x--, y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(0, 0, visited);
    m=-1;
    cout<<q<<endl;
    dfs(q, 0, v);
    cout<<q<<endl;
    cout<<m<<endl;
}

Can anybody tell me what is wrong here because I am getting wrong value of maximum length of the path (m) though the end vertices of the longest path is correct (atleast on the test cases that i have tried). I have tried to implement the following algorithm here:

Algorithm:

  1. Run DFS from any node to find the farthest leaf node. Label that node T.
  2. Run another DFS to find the farthest node from T.
  3. The path you found in step 2 is the longest path in the tree.

Some Test Cases: First:

17
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
8 10
9 11
7 12
7 13
13 14
13 15
15 16
15 17

Correct Answer for this test case is 7.

Second:

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

Correct Answer for this test case is 4.

Upvotes: 1

Views: 6333

Answers (2)

Technoid
Technoid

Reputation: 435

Just remove that count++ from 'for' loop and remove that count--;

And keep 'count++' at the start of fucntion.

void dfs(int i, int count, vector<bool>& v)
{
    count++;
    v[i] = true;
    for(int j=0;j<graph[i].size();j++)
    {
       if(!v[graph[i][j]])
        {
            dfs(graph[i][j], count, v);
        }
    }
    if(count>m)
    {
        m= count;
        q=i;
    } 
}

Upvotes: 1

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

One problem according to me is that you should decrement count immediately on return from the called recursive function.

    for(int j=0;j<graph[i].size();j++)
    {
        if(!v[graph[i][j]])
        {
            count++;                           
            dfs(graph[i][j], count, v);
            count--;
        }

Or simply:

    for(int j=0;j<graph[i].size();j++)
    {
        if(!v[graph[i][j]])           
            dfs(graph[i][j], count+1, v);

This is because the count should not keep incrementing for each neighbour of graph[i].

Upvotes: 3

Related Questions