题解 | #扩散#

一.题目描述

NC545扩散

给出n个结点，n-1条双向边使得结点之间双向连接，有每次操作，每次操作会使会使对应的点和其之间连接的点的点权加一，求m次操作过后每一个点的的点权是多少？

二.算法一(模拟)

首先我们可以利用二维vector进行存边，对于每一次的m操作，我们可以先将指定结点点权加一，然后对所有和指定结点连接的结点的点权加一，进行m次操作后返回所有点的点权。

下面给出完整代码和注释：

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) {
        vector<vector<int>>mp(n+1);
        //利用二维vector建图
        for(int i=0;i<u.size();i++){
            //建立双向边
            mp[u[i]].push_back(v[i]);
            mp[v[i]].push_back(u[i]);
        }
        vector<int>cn(n,0);//记录每一个点的点权
        for(int i=0;i<m;i++){//进行m次操作
            cn[q[i]-1]++;//当前结点加一
            //使其直接连接的结点的点权加一
            for(int j=0;j<mp[q[i]].size();j++){
                cn[mp[q[i]][j]-1]++;
            }
        }
        //返回每一个点的点权
        return cn;
    }
};

时间复杂度：$O(n\ast m)O(n*m)$O(n∗m)对于每一次遍历最坏需要遍历n次，所以时间复杂度是$O(n*m)。

空间复杂度：$O\left(n\right)O(n)$O(n)需要用vector来储存数组。

三.算法二(逻辑)

前面一种算法我们是利用模拟了m次操作，对于每一次操作我们进行了模拟。但是我们可以逆向思考，对于最后返回的所有点的点权我们可以理解为一个是来自于自身的直接增加另一个是来自于旁边直接联通的点，所以我们可以利用这个特点求出来最后每一个点的点权，下面是完整代码：

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) {
        vector<int>cn(n,0);
        vector<int>vis(n,0);
        for(int i=0;i<m;i++){
            //vis用来记录直接就进行访问的点权加一
            //cn用来记录通过直接连接的点权来进行加一
            vis[q[i]-1]++;
            cn[q[i]-1]++;
        }
        for(int i=0;i<n-1;i++){
            //对每个点的点权进行求和
            cn[u[i]-1]+=vis[v[i]-1];
            cn[v[i]-1]+=vis[u[i]-1];
        }
        return cn;
    }
};

时间复杂度：$O(n+m)O(n+m)$O(n+m)只需要进行两次遍历，时间复杂度比较低。

空间复杂度：$O\left(n\right)O(n)$O(n)需要额外开辟两个数组用来记录点权，不需要建图空间复杂度低于第一种算法。