Single source shortest path (on trees)

PHOTO

Mon Jan 10 2022 06:52:05 GMT+0000 (Coordinated Universal Time)

  // to find the distance of each node from root(single source sorthest path (on tress))
        
        vector g[100001];
        vector visi(100001, 0);
        vector distance(100001);
        
        void dfs(ll v,ll dist){
            visi[v] = 1;
            distance[v] = dist;
        
            for(ll child: g[v])
            {
                if(visi[child]==0)
                    dfs(child,dist+1);
            }
        }

        //the final dist array will give the shortest distance from 'v' node.

COPY

This is only aplicable when graph is a tree graph,i.e there are (n-1) number of edges , no cycle & graph is one single component