Graph/binary 树编码问题 - 找出可以支付晚餐的人数（连通分量？）
Graph/binary tree coding problem - find number of people who can pay for dinner (connected components?)
我正在处理一个编码问题，我的解决方案通过了大约 1/4 的测试用例，但我不知道为什么。
密码挑战是：
There are n people in a company, numbered from 1 to n, and every person (except for one) has a boss.
At a dinner, a subset m from the n people from the company come. You want to figure out how many people could pay for the dinner. A person can only pay for the dinner if their boss (or indirectly any boss above them, so for example their bosses boss) is not present at the dinner.
Input
First line: n and m separated by space
Second line: n integers, integer i denoting that the ith person's boss is person i. If i is 0, the person doesn't have a boss (he is the main boss)
Third line: m integers, denoting the people that come to the dinner
Output
The number of people who could pay for the dinner
Example
6 5
5 4 4 5 0 1
5 1 3 2 4
Answer
1
The main boss is present, he is the only one that can pay.
我想把老板关系做成图表，然后计算不同组件的数量。这是正确的方法吗？我可能有 0 索引错误吗？
我的代码：
class Graph:
def __init__(self, V, ppl):
self.V = V
self.ppl = ppl
self.M = len(ppl)
self.adj = [[] for i in range(self.V)]
self.visited = [False for i in range(self.V)]
def NumberOfconnectedComponents(self):
visited = [False for i in range(self.V)]
count = 0
for v in range(self.M):
if (self.visited[self.ppl[v]] == False):
self.DFSUtil(v)
count += 1
return count
def DFSUtil(self, v):
self.visited[v] = True
for i in self.adj[v]:
if (not self.visited[i]):
self.DFSUtil(i)
def addEdge(self, v, w):
self.adj[v].append(w)
# Driver code
if __name__=='__main__':
n, m = map(int, input().split())
bosses = [int(i) for i in input().split()]
people = [int(i) - 1 for i in input().split()]
g = Graph(n, people)
for person in range(n):
fro = person
to = bosses[person]
if to == 0:
continue
else:
g.addEdge(fro, to - 1)
print(g.NumberOfconnectedComponents())
我的代码出错的例子：
INPUT:
5 3
5 5 4 1 0
1 2 3
CORRECT OUTPUT: 2
MY OUTPUT: 3
观察
有一个隐含的假设，老板关系没有循环：我们不能让 A 和 B 成为对方的老板。而且，因为除了一个人之外，每个人都有一个老板，所以这个图是相连的。换句话说，该图是一棵树。
连通分量
A person can only pay for the dinner if their boss (or indirectly any boss above them, so for eg. their bosses boss) is not present at the dinner.
这意味着您的连通分量方法不会给出正确答案。考虑这个组织结构图：
A (CEO)*
|
B (middle manager)
|
C (line worker)*
标有*的人出席了晚宴。那么显然，A是唯一可以支付的，但是有两个连通分量{A}和{C}。
解决方案提示
一种方法是在深度优先或广度优先搜索中从上到下遍历树（顺序无关紧要）。一旦你遇到一个人 X 在场，你就计算那个人并中止搜索的那个分支：X 可以支付（因为他们上面没有人在场），下面没有人 X 可以支付（因为 X 直接或间接地是他们的老板）。
此解决方案要求您根据输入的父子关系在内存中构建父子关系，但它在理论上最优的 O(n) 时间内运行。 （一个 O(m) 算法会很好，但是读取输入已经是 O(n) 所以它不会给我们带来任何东西。）
您的尝试存在一些问题：
self.ppl 中的信息没有用在应该用的地方。在 NumberOfconnectedComponents 中，变量 v 是 self.ppl 中的索引，但除了 if 条件之外，您错误地将 v 视为一个人（当您通过它到 DFSUtil）。你应该通过 self.ppl[v].DFSUtil 根本不使用 self.ppl，因此它假定 所有 人都在场。count 计算的是 路径的数量 您可以从未访问过的（当前）人那里找到的数量，这不是断开连接的组件的数量。
没问题，但是将人存储为从 0 开始的索引（通过 -1 更正），但在存储老板时却不一样，这也有点奇怪。对于那些您稍后在添加边缘时进行更正（-1）的人。
也没有问题，但是名称self.adj表明您正在存储该列表中节点的children，但实际上，它存储节点的 parent，因此 self.adj[v] 甚至不必是一个列表——一个节点只有一个 parent （或 none）。您当然可以决定使用 adj 来存储 children，但是您的 addEdge 应该交换 u 和 v.
算法
你确实可以使用递归向上树（就像你做的那样），但是你应该计算你找不到（向上）一个在场人数在场的老大。像 visited 这样的东西可以用来避免双重工作：一个字典（或列表）给出已经访问过的节点的答案：
代码
def solve(boss_of, present_people):
boss_is_present = [None] * len(boss_of)
present = set(present_people)
def find_boss(person):
if boss_is_present[person] is None: # undetermined
if boss_of[person] in present: # direct boss is present
boss_is_present[person] = True
elif boss_of[person] == -1: # it is the root
boss_is_present[person] = False
else:
boss_is_present[person] = find_boss(boss_of[person])
return boss_is_present[person]
count = 0
for person in present_people: # edge
if not find_boss(person):
# no higher in hierarchy is present
count += 1
return count
# Driver code
if __name__=='__main__':
n, m = map(int, input().split())
boss_of = [int(i) - 1 for i in input().split()]
present_people = [int(i) - 1 for i in input().split()]
print(solve(boss_of, present_people))
有点晦涩，但在 solve 的末尾，您可以通过返回此表达式来删除 count 的定义：
return len(present_people) - sum(int(find_boss(person))
for person in present_people)
迭代求解
如果输入大小很大，并且树的高度很高，上述解决方案可能会遇到堆栈溢出错误——这可能发生在树退化时，每个老板都有大约 1 个下属。
这是一个维护显式堆栈的迭代解决方案：
def find_boss(person):
stack = []
found = False
while person >= 0 and boss_is_present[person] is None:
stack.append(person)
person = boss_of[person]
if person in present: # boss is present
found = True
break
for person in stack:
boss_is_present[person] = found
return found
return len(present_people) - sum(int(find_boss(person))
for person in present_people)
我正在处理一个编码问题，我的解决方案通过了大约 1/4 的测试用例，但我不知道为什么。
密码挑战是：
There are n people in a company, numbered from 1 to n, and every person (except for one) has a boss.
At a dinner, a subset m from the n people from the company come. You want to figure out how many people could pay for the dinner. A person can only pay for the dinner if their boss (or indirectly any boss above them, so for example their bosses boss) is not present at the dinner.
Input
First line: n and m separated by space
Second line: n integers, integer i denoting that the ith person's boss is person i. If i is 0, the person doesn't have a boss (he is the main boss)
Third line: m integers, denoting the people that come to the dinner
Output
The number of people who could pay for the dinner
Example
6 5 5 4 4 5 0 1 5 1 3 2 4Answer
1The main boss is present, he is the only one that can pay.
我想把老板关系做成图表，然后计算不同组件的数量。这是正确的方法吗？我可能有 0 索引错误吗？
我的代码：
class Graph:
def __init__(self, V, ppl):
self.V = V
self.ppl = ppl
self.M = len(ppl)
self.adj = [[] for i in range(self.V)]
self.visited = [False for i in range(self.V)]
def NumberOfconnectedComponents(self):
visited = [False for i in range(self.V)]
count = 0
for v in range(self.M):
if (self.visited[self.ppl[v]] == False):
self.DFSUtil(v)
count += 1
return count
def DFSUtil(self, v):
self.visited[v] = True
for i in self.adj[v]:
if (not self.visited[i]):
self.DFSUtil(i)
def addEdge(self, v, w):
self.adj[v].append(w)
# Driver code
if __name__=='__main__':
n, m = map(int, input().split())
bosses = [int(i) for i in input().split()]
people = [int(i) - 1 for i in input().split()]
g = Graph(n, people)
for person in range(n):
fro = person
to = bosses[person]
if to == 0:
continue
else:
g.addEdge(fro, to - 1)
print(g.NumberOfconnectedComponents())
我的代码出错的例子：
INPUT:
5 3
5 5 4 1 0
1 2 3
CORRECT OUTPUT: 2
MY OUTPUT: 3
观察
有一个隐含的假设，老板关系没有循环：我们不能让 A 和 B 成为对方的老板。而且，因为除了一个人之外，每个人都有一个老板，所以这个图是相连的。换句话说，该图是一棵树。
连通分量
A person can only pay for the dinner if their boss (or indirectly any boss above them, so for eg. their bosses boss) is not present at the dinner.
这意味着您的连通分量方法不会给出正确答案。考虑这个组织结构图：
A (CEO)*
|
B (middle manager)
|
C (line worker)*
标有*的人出席了晚宴。那么显然，A是唯一可以支付的，但是有两个连通分量{A}和{C}。
解决方案提示
一种方法是在深度优先或广度优先搜索中从上到下遍历树（顺序无关紧要）。一旦你遇到一个人 X 在场，你就计算那个人并中止搜索的那个分支：X 可以支付（因为他们上面没有人在场），下面没有人 X 可以支付（因为 X 直接或间接地是他们的老板）。
此解决方案要求您根据输入的父子关系在内存中构建父子关系，但它在理论上最优的 O(n) 时间内运行。 （一个 O(m) 算法会很好，但是读取输入已经是 O(n) 所以它不会给我们带来任何东西。）
您的尝试存在一些问题：
self.ppl中的信息没有用在应该用的地方。在NumberOfconnectedComponents中，变量v是self.ppl中的索引，但除了if条件之外，您错误地将v视为一个人（当您通过它到DFSUtil）。你应该通过self.ppl[v].DFSUtil根本不使用self.ppl，因此它假定 所有 人都在场。count计算的是 路径的数量 您可以从未访问过的（当前）人那里找到的数量，这不是断开连接的组件的数量。
没问题，但是将人存储为从 0 开始的索引（通过 -1 更正），但在存储老板时却不一样，这也有点奇怪。对于那些您稍后在添加边缘时进行更正（-1）的人。
也没有问题，但是名称self.adj表明您正在存储该列表中节点的children，但实际上，它存储节点的 parent，因此 self.adj[v] 甚至不必是一个列表——一个节点只有一个 parent （或 none）。您当然可以决定使用 adj 来存储 children，但是您的 addEdge 应该交换 u 和 v.
算法
你确实可以使用递归向上树（就像你做的那样），但是你应该计算你找不到（向上）一个在场人数在场的老大。像 visited 这样的东西可以用来避免双重工作：一个字典（或列表）给出已经访问过的节点的答案：
代码
def solve(boss_of, present_people):
boss_is_present = [None] * len(boss_of)
present = set(present_people)
def find_boss(person):
if boss_is_present[person] is None: # undetermined
if boss_of[person] in present: # direct boss is present
boss_is_present[person] = True
elif boss_of[person] == -1: # it is the root
boss_is_present[person] = False
else:
boss_is_present[person] = find_boss(boss_of[person])
return boss_is_present[person]
count = 0
for person in present_people: # edge
if not find_boss(person):
# no higher in hierarchy is present
count += 1
return count
# Driver code
if __name__=='__main__':
n, m = map(int, input().split())
boss_of = [int(i) - 1 for i in input().split()]
present_people = [int(i) - 1 for i in input().split()]
print(solve(boss_of, present_people))
有点晦涩，但在 solve 的末尾，您可以通过返回此表达式来删除 count 的定义：
return len(present_people) - sum(int(find_boss(person))
for person in present_people)
迭代求解
如果输入大小很大，并且树的高度很高，上述解决方案可能会遇到堆栈溢出错误——这可能发生在树退化时，每个老板都有大约 1 个下属。
这是一个维护显式堆栈的迭代解决方案：
def find_boss(person):
stack = []
found = False
while person >= 0 and boss_is_present[person] is None:
stack.append(person)
person = boss_of[person]
if person in present: # boss is present
found = True
break
for person in stack:
boss_is_present[person] = found
return found
return len(present_people) - sum(int(find_boss(person))
for person in present_people)