algorithm - 感染者寻找算法

Question

我有一个算法可以解决给定输入中的“受影响的人”。我必须解决受影响人员的名单。人们用数字表示，两个人在给定时间 N 相互交互。如果其中一个人受到影响，另一个人也会受到影响。

首先，给出N(人数)和M(总交互)。然后 (P1 P2 time) 在 M 行中给出。

例如，5 5

2 3 1

1 2 2

3 4 2

1 3 3

2 5 4

已给出。

这意味着有 5 个人，他们有 5 次互动，后面有 5 行表示第 2 个人和第 3 个人在时间 1 会面，第 1 和 2 在第 2 次会面，第 3 和 4 个人在第 2 次会面，依此类推.(时间可能无法排序)。

一开始，人 1 总是被感染。

所以在时间 2，人 1 和 2 相遇，使人 2 被感染，人 1 和 3 在时间 3 相遇，使人 3 被感染，最后，人 2 和 5 在时间 4 相遇，使人 5 被感染。

这使得 1, 2, 3, 5 最后被感染。

交互是按时间发生的，多个交互可以同时发生，如果是这样的话，就得考虑大多数人了受到影响。

例如，如果第 1 人和第 3 人被感染，并且 (4 6 3) (3 6 3) 作为输入，则必须首先计算 (3 6 3) 以使第 6 人被感染，第 4 人被感染为好吧。

为了解决这个问题，我创建了这个算法，它的运行时间很糟糕，我需要帮助优化这个算法。

inputs = input()
peopleNum = int(inputs.split()[0])
times = int(inputs.split()[1])
peopleMeet = {}
affectedPeople = [1]
for i in range(times):
    occur = input()
    person1 = int(occur.split()[0])
    person2 = int(occur.split()[1])
    time = int(occur.split()[2])
    if not time in peopleMeet:
        peopleMeet[time] = [(person1, person2)]
    else:
        for occur in range(len(peopleMeet[time])):
            if set(peopleMeet[time][occur]) & set((person1,person2)):
                peopleMeet[time][occur] = peopleMeet[time][occur] + ((person1,person2,))
                break
            if occur == (len(peopleMeet[time]) - 1):
                peopleMeet[time].append((person1,person2))
for time in sorted(peopleMeet):
    for occur in peopleMeet[time]:
        if set(affectedPeople) & set(occur):
            affectedPeople.extend(list(occur))
print(' '.join([str(x) for x in set(affectedPeople)]))

我是 stack overflow 的新手，我不习惯格式和发布指南，所以如果我错了，我很抱歉。提前谢谢你。

Answer 1

伪代码:

affectedPeople = bool array of size N + 1, initialized at false
affectedPeople[1] = True
sort the interactions based on time
iterate interactions and group them by time
for each group x:
    create a graph with interactions from that group as edges
    do a dfs on each affectedPeople present on these interactions. All the reached nodes will be affected
    add these nodes to affectedPeople (set them to True)
count amount of i with affectedPeople[i] = True