无向图红黑染色(相邻不同为红)的方案数
哪些公司问过
答案要点
- 红色节点构成独立集,方案数等于独立集个数(含全黑)
- 一般图精确计数没有已知多项式算法,常用回溯枚举
- 染红前检查已染色邻居,可按度数排序加强剪枝
- 各连通分量独立计算后相乘
- 树上用树形 DP:f[v][0] = Π(f[c][0]+f[c][1]),f[v][1] = Π f[c][0]
易错点
- 把题目当成普通二分图染色,要求相邻颜色都不同
- 漏掉全部染黑这一种方案
- 多个连通分量时把方案数相加而不是相乘
面试官常见追问
- 如果图是一条链或一个环呢?
- 节点数在 40 左右怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。