题解 | #连通块#

连通块

http://www.nowcoder.com/practice/5b2ed1c316fc42a0b974ff2b264fa922

题意：

有一个n个节点的树，每个节点的值为 $xi$ 。

将n个节点划分成k个互相不连通的区域，希望这k个区域内部的值之和都大于等于m，问是否可行？

输出 $true \ or \ false.$

方法一：

dfs

思路：直接深搜模拟。

      首先，建图(无向边)；

        通过后序遍历去计算每个子树的sum之和。

      如果sum>=m,则连通块个数cnt减一，并将这个子树的值置为0（即return 0）;

      否则，直接return sum。

      最后判断   连通块个数cnt是否==0,如果是，则置flag=true,表示成功。

class Solution {
public:
    bool flag=false;//标记，判断是否成功
    int cnt;//连通块个数
    
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<vector<int>> g(n+1);//图
        vector<int> vis(n+1,0);//某节点是否访问过
        cnt=k;//k个连通块
        
        int num=u.size();
        for(int i=0;i<num;i++){//建图
            g[u[i]].push_back(v[i]);//无向图
            g[v[i]].push_back(u[i]);
        }
        vis[1]=1;//节点1已访问
        dfs(g, x, n, m,1,vis);
        return flag;
        
    }
    
    int dfs(vector<vector<int>> g,vector<int>& x,int n,int m,int st,vector<int> vis){

        int sum=x[st-1];//当前节点st的值
        
        int num=g[st].size();
        for(int i=0;i<num;i++){//遍历当前节点st相连的节点
            int t=g[st][i];
            if(vis[t]==0){//如果未访问过，则访问
                vis[t]=1;
                sum+=dfs(g,x,n,m,t,vis);
                if(cnt==0)//如果满足连通块==0,直接return,这里的-1无意义
                    return -1;
                vis[t]=0;
            }
        }
        if(sum>=m){//如果以当前节点st为根节点的子树满足>=m
            cnt--;//则连通块减一
            if(cnt==0){//如果满足连通块==0，则flag=true表示成功，并return，这里的-1无意义
                flag=true;
                return -1;
            }
            return 0;//返回0
        }else{
            return sum;//否则返回以当前节点st为根节点的子树的值
        }
    }
};

时间复杂度： $O(n)，遍历n个节点$

空间复杂度： $O(n^{2}),n是节点个数，建图$

方法二：

bfs

思路：根据方法一中dfs的后序遍历思想，可以等效于从叶子节点bfs。

将叶子节点入队列，从下往上广搜。

sum[]表示以某号节点为根节点的子树的值之和。

class Solution { public: bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) { vector<vector<int>> g(n+1);//图 vector<int> vis(n+1,0);//某节点是否访问过 vector<int> degree(n+1,0);//记录每个节点的度数 vector<int> sum(n+1,0);//某个节点构成的子树的值之和 int num=u.size(); for(int i=0;i<num;i++){//建图 g[u[i]].push_back(v[i]);//无向图 g[v[i]].push_back(u[i]); degree[u[i]]++;//度数加一 degree[v[i]]++; } queue<int> q; for(int i=1;i<=n;i++){ sum[i]=x[i-1];//将本身值赋给sum[] if(degree[i]==1){//叶子节点进队列 q.push(i); vis[i]=1; } } while(!q.empty()){ int now=q.front(); q.pop(); if(sum[now]>=m){//如果以当前节点为根节点的子树满足>=m sum[now]=0;//值赋为0，表示截断 k--;//连通块减一 if(k==0)//如果连通块个数==0，则成功 return true; } int num=g[now].size(); for(int i=0;i<num;i++){ int t=g[now][i]; sum[t]+=sum[now];//父节点加上这个子节点的值 if(vis[t]==0){//如果未访问过，则进队列 vis[t]=1; q.push(t); } } } return false; } };

时间复杂度： $O(n)，遍历n个节点$

空间复杂度： $O(n^{2}),n是节点个数，建图$