题解 | #连通块#
连通块
http://www.nowcoder.com/practice/5b2ed1c316fc42a0b974ff2b264fa922
题意：
有一个n个节点的树，每个节点的值为
。
将n个节点划分成k个互相不连通的区域，希望这k个区域内部的值之和都大于等于m，问是否可行？
输出 
方法一：
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为根节点的子树的值
}
}
};
时间复杂度：%EF%BC%8C%E9%81%8D%E5%8E%86n%E4%B8%AA%E8%8A%82%E7%82%B9)
空间复杂度：%2Cn%E6%98%AF%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0%EF%BC%8C%E5%BB%BA%E5%9B%BE)
方法二：
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;
}
};
时间复杂度：
空间复杂度：
