太原网站建设哪家便宜,免费官方网站创建,高端品牌衣服排行榜前十名,学校门户网站群建设方案美团2024届秋招笔试第一场编程真题
先提一个小知识#xff1a;题目中凡是提到树结构都要使用图的存储方式#xff0c;只有二叉树例外。
分析#xff1a;在树结构中#xff0c;孩子和父节点是相邻节点#xff0c;而父节点可能有多个孩子节点。在染色的过程中#xff0c;…美团2024届秋招笔试第一场编程真题
先提一个小知识题目中凡是提到树结构都要使用图的存储方式只有二叉树例外。
分析在树结构中孩子和父节点是相邻节点而父节点可能有多个孩子节点。在染色的过程中本质是父子节点满足条件就染成红色。具体染色策略以下图为例 图中节点权值均为1也就是任意相邻节点都可以满足染色条件显然我们不能先将a和b染色那样就只有2个点能被染色而是应该先染色f,b或 e,b然后再a,c 或a,d这样可以染4个点。下图又该先考虑染色那些节点呢 这样总结出贪心策略先处理叶子结点的染色然后处理内部节点。比如上图先处理g,f。如果能染色哪么将g,f标记红色同时f,b就不可能染色了如果不能染色未来还可以继续试探f,b。
实现方法先处理最外层节点叶子外层处理完了这些叶子就可以不要了往内层推进。
使用拓扑排序的思想。当然不是入度0节点入队这可不是有向图。而是度为1叶子节点入队从树叶向树根进行拓扑处理。
图问题的复杂度正常都是遍历所有的结点也就是访问所有的点和边此图n-1条边复杂度为O(n)。
#include bits/stdc.h
typedef long long ll;
using namespace std;
ll n,a[100005],d[100005],red[100005],v[100005],ans0;
vector int e[100005];
bool isP(ll x)/** 平方数判定 */
{ll y(int)sqrt(x);return y*yx;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y;cinn;for(i1;in;i)cina[i];for(i1;in;i){cinxy;e[x].push_back(y),e[y].push_back(x);d[x],d[y];/** d数组统计度 */}queueintq;for(i1;in;i)if(d[i]1)/** 度为1的入队*/q.push(i);while(q.size())/** 模拟拓扑排序处理方法 */{xq.front();v[x]1;/** 标记这个节点避免重新被入队处理 */q.pop();for(i0;ie[x].size();i)/** 找到x所有邻接点 */{ye[x][i];if(v[y]) /** y已经访问过其实y一定是x的子节点 */continue;if(red[x]0red[y]0isP(a[x]*a[y]))/** x和它父节点y满足条件 */red[x]red[y]1,ans2;/** 标记颜色计数器2 */d[y]--;if(d[y]1)/** 度为1说明y子节点都处理完了此时可以入队 */q.push(y);}}coutans;return 0;
}
