I can't believe i beats 100% use dfs to Find the longest path in the graph


  • -1
    X

    when I first met the problem , i thought dfs is a proper way to get the longest way for all odes.and it takes O(N*N) times, wit no doubt i get a time limit error , so i think is it necessary to dfs ever node in the graph to get the longest path?
    certainly no ,maybe not certainly, i really think a lot of time

    we got several node 0 1 2 3 4 5 6 7 8`````

    1.we first search 0 and got a node end of the path represent the longest path1 and the MaxLen1.

    2.second we search the end get from the 1st step,we got the other side of the longest path and get new end' and Maxlen2,path2

    and the path2 maybe the longest path of tht graph, and the end may be the path's two side.

    class Solution {
        int endv;
        int maxlen =0 ;
        void dfs(int node,vector<vector<int>>& path,vector<bool>& visit,vector<int> &route,int len,vector<int>& tmp)
        {
            visit[node] = true;
            len++;
    //        route.push_back(node);
            tmp.push_back(node);
            int nextnode;
            int edgenum = path[node].size();
            for (int i =0; i<edgenum; i++) {
                nextnode = path[node][i];
                if (visit[nextnode] == false) {
                    visit[nextnode] = true;
                    dfs(nextnode, path, visit,route, len,tmp);
                   
                    visit[nextnode] = false;
                }
                if (len > maxlen) {
                        maxlen = len;
                        endv = node;
                    route = tmp;
                    }
            }
            tmp.pop_back();
            visit[node] = false;
        }
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<bool> visited(n,false);
            vector<int> route;
            vector<int> tmp;
            int pathsize = edges.size();
            vector<int>res;
            if (n<=2) {
                res.push_back(0);
                if (n == 2) {
                    res.push_back(1);
                }
                return res;
            }
            vector<vector<int>> path(n);
            for (int i =0; i<pathsize ; i++) {
                path[edges[i].first].push_back(edges[i].second);
                path[edges[i].second].push_back(edges[i].first);
            }
            dfs(0, path, visited,route,0,tmp);
            route.clear();
            dfs(endv, path, visited, route, 0,tmp);
          
            if (maxlen%2 == 0) {
                res.push_back(route[maxlen/2]);
                res.push_back(route[maxlen/2-1]);
            }
            else
                res.push_back(route[maxlen/2]);
    
            return res;
            
    //        for (int i =0; i<n; i++) {
    //            len = 1;
    //            visited[i] = true;
    //            len = dfs(i,path,visited,1);
    //            visited[i] =false;
    //            allpath[len].push_back(i);
    //        }
    
        }
    };

  • 0
    C

    does not pass the following test:
    6
    [[3,4],[3,5],[1,0],[1,2],[1,3]]


  • 0
    X

    Yeah i found i paste the old code from editor ,and it leak some lines,ihave modified it,please help me check it~~~


Log in to reply
 

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