Maximum product of two non-intersecting paths in a tree - dfs graph

disjoint_paths_graph.cpp

#include <bits/stdc++.h> 
using namespace std; 

void dfs1(vector<int> g[],int visit[],int curr,int len,int *max,int* node){
    if(len > *max){
        *max = len;
        *node = curr;
    }
    visit[curr] = 1;
    for(auto i= g[curr].begin();i!=g[curr].end();i++){
        if(visit[*i] == 0){
            dfs1(g,visit,*i,len+1,max,node);
        }
    }
    visit[curr] = 0;
}

void dfs2(vector<int> g[],int visit[],int curr,int len,int *max){
    if(len > *max){
        *max = len;
    }
    visit[curr] = 1;
    for(auto i= g[curr].begin();i!=g[curr].end();i++){
        if(visit[*i] == 0)
            dfs2(g,visit,*i,len+1,max);
    }
    visit[curr] = 0;
}

int maxProductOfTwoPaths(vector<int> g[], int N) 
{ 
    int visit[N+2];
    memset(visit,0,sizeof(visit));
    int ans =0;
	for(int i=1;i<=N+1;i++){
	    for(int j=0;j<g[i].size();j++){
	        
	        visit[g[i][j]] =1;
	        int path1=0;
	        int node = i;
	        dfs1(g,visit,i,0,&path1,&node);
	        dfs2(g,visit,node,0,&path1);
	        visit[g[i][j]] = 0;
	        
	        int path2 = 0;
	        visit[i] =1;
	        node = g[i][j];
	        dfs1(g,visit,g[i][j],0,&path2,&node);
	        dfs2(g,visit,node,0,&path2);
	        visit[i] =0;
	        
	        ans = max(ans,path1*path2);
	        cout<<path1<<" "<<path2<<","<<i<<" "<<g[i][j]<<"\n";
	    }
	}
	return ans;
} 

void addEdge(vector<int> g[], int u, int v) 
{ 
	g[u].push_back(v); 
	g[v].push_back(u); 
} 

int main() 
{ 
	int edges[][2] = {{1, 8}, {2, 6}, {3, 1}, 
					{5, 3}, {7, 8}, {8, 4}, 
					{8, 6} }; 
		 

	int N = sizeof(edges)/sizeof(edges[0]); 

	vector<int> g[N + 2]; 
	for (int i = 0; i < N; i++) 
		addEdge(g, edges[i][0], edges[i][1]); 

	cout << maxProductOfTwoPaths(g, N) << endl; 
	return 0; 
} 

Given an undirected connected tree with N nodes (and N-1 edges), we need to find two paths in this tree such that they are non-intersecting and the product of their length is maximum.

Example:
In the tree two paths which are non-intersecting and have the highest product are, 1-3-5 and 7-8-6-2 (or 4-8-6-2), so the answer is 3*2 = 6.

  4
  |
7-8-6-2
  |
  1-3-5

Since tree is connected and paths are non-intersecting, If we take any pair of such paths there must be a third path, connecting these two and If we remove an edge from the third path then tree will be divided into two components — one containing the first path, and the other containing the second path. This observation suggests us the algorithm: iterate over the edges; for each edge remove it, find the length of the path in both connected components and multiply the lengths of these paths.

Idea of removing is same as performing dfs on one node of the edge while the other one is already marked visited. While performing dfs will give the longest length from the current node, it will not be the longest length in the subtree. To find the longest length, perform dfs finding max length two times. First, dfs will find the max length from the node of the deleted edge. Second dfs will start from this node and it will give the max length in the subtree.