收集树上所有苹果的最小时间

落日映苍穹つ 2023-10-06 14:11 7阅读 0赞

## 收集树上所有苹果的最小时间 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]

#### 思路： ####

从苹果节点不断向父节点的方向走

需要解决的是：  
1.得到每个节点的父节点  
2.防止在向父节点走时重复计算

首先由题设输入构造邻接表，已知节点0是根节点，由此可通过dfs得到所有节点的根节点，保存在vector中

构建dfs函数，由于邻接表为无向图的邻接表，为防止两节点互相认作父节点，参数中需包含上次遍历的根节点，dfs函数中的邻接表参数注意得是传引用，若是传值调用，每次调用都会发生拷贝构造，会导致超时

为防止在向父节点走时重复计算，使用visited数组保存已访问过的节点，遍历所有节点，若为苹果节点且未被访问过，开始不断向父节点方向走，从苹果节点开始走到第一个已被访问的节点或走到根节点即停止，注意向父节点走的循环为do…while循环

将得到的结果\*2后返回

#### 代码： ####

class Solution {
        
    public:
        void get_father( vector<vector<int>>& adj,int i,int pre,vector<int>& father )
        {
           
            father[ i ]=pre;
            for( int& x:adj[i] )
            {
           
                if( x!=pre )
                {
        
                    get_father( adj,x,i,father );
                }      
            }
        }
        int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        
            vector<vector<int>> adj(n);
            vector<int> father(n);
            vector<bool> visited(n,false);
            int i;
            for( vector<int>& x:edges )
            {
        
                adj[ x[0] ].push_back( x[1] );
                adj[ x[1] ].push_back( x[0] );
            }
            get_father( adj,0,-1,father );
            int ans=0;
            for( i=0;i<n;i++ )
            {
        
                if( hasApple[i] && !visited[i]  )
                {
        
                    int j=i;
                    if( i==0 )
                        continue;
                    do
                    {
        
                        ans++;
                        visited[ j ]=true;
                        j=father[j];
                    }while( j!=0 && !visited[j] );
                }
            }
            return ans*2;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020080316444265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200803164458191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200803164510269.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70