雪花店面第二轮

第二轮，是个烙印，开头自我介绍，稍微聊了一下专业，感觉还不错，但是进入coding以后，面试官全程没有提供任何hint，并且我认为负面地影响了我的发挥（当然也是我心态不好）。题目是给定一些location，还有一些color，以及一些连接两个location的edges，要给location染色，使得相邻location之间染的颜色不同。简而言之：给定无向图，对无向图进行k染色，k是颜色数量，使得相邻节点颜色不同。因为我是搞竞赛的，所以一开始先入为主在想是否有什么算法可以较优的解决这个问题（感觉面试比较烦的一点就是没有数据范围，竞赛的时候往往可以快速通过数据范围确定使用的算法），大概思考了十分钟，想不出什么好办法，感觉只能暴力枚举计算，于是就和面试官说可以这样暴力枚举。然后我忽然想到，这个染色问题似乎是个NP问题，没有多项式解法，于是我就和面试官说，如果我没记错这应该是个NP问题，结果面试官反驳我说不是NP（这个时候我心态就有点崩了

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

正最后没调出来，写代码的全程他也没有任何交流或者沟通，即使我有试图想和他沟通思路（以确保我在right track上），他也一直一言不发，所以变成我在那里自言自语。反正肯定是挂了，感觉有点可惜。分享不易，求米！！！

不是785，难多了

时间复杂度我说的是O(k^N)，上面打错了

Leetcode 785?

匿名用户 发表于 2023-9-30 01:10
Leetcode 785?

不是，这里是要一个对无向图k染色的方案（可能不存在合法方案），不是判断二分图，785是可以用二染色法判断是不是二分图

https://www.geeksforgeeks.org/3-coloring-is-np-complete/

dfs，用C++写的：

1. // invariant: upon entry, color[index] is already colored.
   
2. bool helper(const vector<vector<int>>& g, vector<int>& color, int index, int k) {
   
3.   for (int child : g[index]) {
   
4.     if (color[child] == color[index]) return false;
   
5.     else if (color[child] != 0) continue;
   
6.     // color[child] == 0
   
7.     for (int c = 1; c <= k; c++) {
   
8.       if (c == color[index]) continue;
   
9.       color[child] = c;
   
10.       if (helper(g, color, child, k)) break;
    
11.       color[child] = 0;
    
12.     }
    
13.     // impossible to color child.
    
14.     if (color[child] == 0) return false;
    
15.   }
    
16.   return true;
    
17. }
    
18. 
    
19. vector<int> k_color(const vector<vector<int>>& g, int k) {
    
20.   int n = g.size();
    
21.   vector<int> color(n);
    
22.   for (int i = 0; i < n; i++) {
    
23.     if (color[i] == 0) color[i] = 1;
    
24.     if (!helper(g, color, i, k)) return {};
    
25.   }
    
26.   return color;
    
27. }

复制代码

暴力DFS枚举行不行？

想了一下，只能暴力枚举