新同事才来5天就被开除了，就因为他每天按时下班。。
(关注数据结构和算法，了解更多新知识)
最近一网友发文称：新同事才来5天就被开除了，原因是他每天按时下班。
加班这事对于上班的人来说已经司空见惯了，有些人估计经常加班。也有不少公司甚至把加班当做一种企业文化，下班之后不到一个小时基本上没人动。
我记得在2014年的时候有一个项目也是加班加点的赶，每天晚上都是11点之后才能回去，后来也是新来了一个同事，下班之后偷偷问我，为啥大家都不走，我看了看其他人笑了笑没说，结果每等一个小时就会问我一次，终于等到11点多才开始下班，结果第二天就没来了。
之前我也经常在公司说不能让加班成为一种企业文化，而领导说项目发布的时间都是定好的，规定时间必须要完成（当时做的是app开发，实际上就是app的版本更新）。当时一位同事给我说了一句很经典的话，他说版本更新又不是女人生孩子，时间到了必须得生，版本什么时候更新都是领导一句话的事，为什么不能延迟。
要想整顿职场，我觉得还是得靠零零后，我们来看下各位网友的评论。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第2368题：受限条件下可到达节点的数目，我们来看下。
问题描述
难度：中等
现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示受限节点。
在不访问受限节点的前提下，返回你可以从节点 0 到达的最多节点数目。注意，节点 0 不会标记为受限节点。
输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。
输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。
2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树
1 <= restricted.length < n
1 <= restricted[i] < n
restricted 中的所有值 互不相同
问题分析
public int reachableNodes(int n, int[][] edges, int[] restricted) {
// n个集合，记录与每一个节点相连的所有节点
List<Integer>[] lists = new List[n];
for (int i = 0; i < n; i++)// 初始化集合
lists[i] = new ArrayList();
for (int[] edge : edges) {
// 因为是无向图，所以如果a和b相连，那么b也和a相连。
lists[edge[0]].add(edge[1]);
lists[edge[1]].add(edge[0]);
}
// 记录受限的节点和已经访问过的节点
boolean[] isRestricted = new boolean[n];
for (int restrict : restricted)
isRestricted[restrict] = true;
return dfs(0, lists, isRestricted);
}
private int dfs(int start, List<Integer>[] lists, boolean[] isRestricted) {
if (isRestricted[start])// 如果是受限的节点或者是已经访问过的节点，直接跳过
return 0;
isRestricted[start] = true;// 标记为已访问
int res = 1;
for (int num : lists[start])// 递归和当前节点相连的所有节点。
res += dfs(num, lists, isRestricted);
return res;
}
public:
int reachableNodes(int n, vector<vector<int>> &edges, vector<int> &restricted) {
vector<vector<int>> lists(n); // n个集合，记录与每一个节点相连的所有节点
for (auto &edge: edges) {
// 因为是无向图，所以如果a和b相连，那么b也和a相连。
lists[edge[0]].push_back(edge[1]);
lists[edge[1]].push_back(edge[0]);
}
// 记录受限的节点和已经访问过的节点
vector<bool> isRestricted(n);
for (int restrict: restricted)
isRestricted[restrict] = true;
return dfs(0, lists, isRestricted);
}
int dfs(int start, vector<vector<int>> &lists, vector<bool> &isRestricted) {
if (isRestricted[start])// 如果是受限的节点或者是已经访问过的节点，直接跳过
return 0;
isRestricted[start] = true;// 标记为已访问
int res = 1;
for (int num: lists[start])// 递归和当前节点相连的所有节点。
res += dfs(num, lists, isRestricted);
return res;
}
int dfs(int start, int **lists, int *listsColSize, bool *isRestricted) {
if (isRestricted[start])// 如果是受限的节点或者是已经访问过的节点，直接跳过
return 0;
isRestricted[start] = true;// 标记为已访问
int res = 1;
for (int i = 0; i < listsColSize[start]; ++i)// 递归和当前节点相连的所有节点。
res += dfs(lists[start][i], lists, listsColSize, isRestricted);
return res;
}
int reachableNodes(int n, int **edges, int edgesSize, int *edgesColSize, int *restricted, int restrictedSize) {
// n个集合，记录与每一个节点相连的所有节点
int **lists = malloc(sizeof(int *) * n);
int *listsColSize = calloc(n, sizeof(int));// 提前计算，防止内存不够
for (int i = 0; i < edgesSize; ++i) {
listsColSize[edges[i][0]]++;
listsColSize[edges[i][1]]++;
}
// 初始化集合
for (int i = 0; i < n; ++i)
lists[i] = malloc(sizeof(int) * listsColSize[i]);
memset(listsColSize, 0, n * sizeof(int));// 重置
for (int i = 0; i < edgesSize; ++i) {
// 因为是无向图，所以如果a和b相连，那么b也和a相连。
lists[edges[i][0]][(listsColSize[edges[i][0]])++] = edges[i][1];
lists[edges[i][1]][(listsColSize[edges[i][1]])++] = edges[i][0];
}
// 记录受限的节点和已经访问过的节点
bool *isRestricted = calloc(n, sizeof(bool));
for (int i = 0; i < restrictedSize; ++i)
isRestricted[restricted[i]] = 1;
int res = dfs(0, lists, listsColSize, isRestricted);
// 内存释放
for (int i = 0; i < n; ++i)
free(lists[i]);
free(lists);
free(listsColSize);
free(isRestricted);
return res;
}
def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
def dfs(start: int, lists: List[List[int]], isRestricted: List[bool]):
if isRestricted[start]: # 如果是受限的节点或者是已经访问过的节点，直接跳过
return 0
isRestricted[start] = True # 标记为已访问
res = 1
for num in lists[start]: # 递归和当前节点相连的所有节点。
res += dfs(num, lists, isRestricted)
return res
# n个集合，记录与每一个节点相连的所有节点
lists = [[] for _ in range(n)]
# 因为是无向图，所以如果a和b相连，那么b也和a相连。
for edge in edges:
lists[edge[0]].append(edge[1])
lists[edge[1]].append(edge[0])
# 记录受限的节点和已经访问过的节点
isRestricted = [0] * n
for restrict in restricted:
isRestricted[restrict] = True
return dfs(0, lists, isRestricted)