Two Pass DFS C++ Solution by finding longest path in the graph (Very Easy)


  • 0
    B
    class Solution {
    public:
        int max_len;
        int v;
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<vector<int> > graph(n);
            for(int i = 0 ; i < edges.size(); i++){
                graph[edges[i].first].push_back(edges[i].second);
                graph[edges[i].second].push_back(edges[i].first);
            }
            vector<bool> visited(n,false);
            vector<int> path;
             
            dfs(graph,visited,0,0,path);
            
            max_len = 0;
            path.clear();
            dfs(graph,visited,v,0,path);
           
            vector<int> res;
            if(max_len % 2 == 0){
                res.push_back(path[max_len/2]);
                res.push_back(path[max_len/2-1]);
            }
            else{
                res.push_back(path[max_len/2]);
            }
            return res;
        }
        
        void dfs(vector<vector<int> >& graph, vector<bool>& visited, int i, int count, vector<int>& path){
            
            visited[i] = true;
            count++;
            path.push_back(i);
            
            
            for(auto it = graph[i].begin(); it != graph[i].end(); it++){
                if(!visited[*it]){
                    dfs(graph,visited,*it,count,path);
                }
            }
            
            if(count > max_len){
                max_len = count;
                v = i;
            }
            visited[i] = false;
        }
    };

  • 0
    X

    I think your solution is wrong... but I'm not sure as it passes all the test cases.

    In your second dfs, you need to log Path, however how do you interpret your Path? I think that's just visiting order, so you can't use middle nodes of Path as results.

    Did I miss anything? Can you explain what is your Path?


  • 0
    Y

    this code goes wrong with input:

    6
    [[4,0],[4,2],[1,3],[3,5],[3,2]].


  • 0
    Y

    @yttdebaba2
    Record the parent of the node instead of 'path' would be ok.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.