感染者查找算法

Question

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

首先给出了总交互次数N( of people)和总交互次数M(total interactions)。然后在M线路上给出(P1 P2 )时间。

例如，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被感染。

这会使person 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)]))

我在堆栈溢出方面非常新手，而且我不习惯格式化和发布指南，所以如果我错了，我很抱歉。提前谢谢你。

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

Answer 2

解决这个问题的另一种方法是使用运行时复杂度为O(n*log(n))的union-find算法。这个想法非常简单明了：

• 根据时间参数按升序对给定输入进行排序。
• 按时间对交往进行分组，并为每个组迭代交往并合并参与其中的人员。如果制定的组受到感染，联合操作中的
• 将保留信息(请参阅代码，以便更好地查找此组中参与交互的每个人，检查他是否属于受感染的组，并将他标记为已感染。
• 将此组中涉及的人员的联合查找状态重置为原始状态，以便我们可以继续重新处理其他组，同时保留有关当前受感染人员的信息。

下面是相同的代码：

MAX_N = 1000

parent = list(range(MAX_N))
infected = [False] * MAX_N

def find(x):
    if x == parent[x]: return x
    parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    parent_x = find(x)
    parent_y = find(y)

    # If either of the two clusters we're joining is infected
    # Infect the combined cluster as well
    infected[parent_y] = infected[parent_x] or infected[parent_y]
    parent[parent_x] = parent_y

def solve(inputs):
    infected[1] = True
    # Sort the input by the time parameter
    inputs.sort(key=lambda x: x[2])
    answer_set = set()

    i = 0
    while i < len(inputs):
        persons = set()
        cur_time =  inputs[i][2]

        # Iterate over interactions belonging to the same group i.e. same time
        while i < len(inputs) and inputs[i][2] == cur_time:
            person_x = inputs[i][0]
            person_y = inputs[i][1]

            persons.add(person_x)
            persons.add(person_y)

            # Union the people involed in the interaction
            union(person_x, person_y)
            i += 1

        for person in persons:
            group = find(person)
            # If the person belongs to an infected group, he's infected as well
            if infected[group]: 
                infected[person] = True
                answer_set.add(person)

        # Reset the union-find state as we move to the next time step
        for person in persons:
            parent[person] = person

    return answer_set

print (solve([[2, 3, 1], [1, 2, 2], [1, 3, 3], [2, 5, 4], [3, 4, 2]]))

Answer 3

请参阅代码中的注释：

DATA = [[2, 3, 1], [1, 2, 2], [3, 4, 2], [1, 3, 3], [2, 5, 4]]

# status contains the contamination status for each people in the dataset
# At the begining we will have only [1] contaminated so: 
# {1: True, 2: False, 3: False, 4: False, 5: False}
people_status = {}
for people_id in set(x[0] for x in DATA).union(x[1] for x in DATA):
    people_status[people_id] = people_id == 1

# meeting contains DATA grouped by time so with this dataset we will have:
# {1: [[2, 3]], 2: [[1, 2], [3, 4]], 3: [[1, 3]], 4: [[2, 5]]}
meeting = {}
for x in DATA:
    if x[2] in meeting:
        meeting[x[2]].append(x[:2])
    else:
        meeting[x[2]] = [x[:2]]


# now we just have to update people_status while time evolve
for time in sorted(meeting.keys()):
    while True:
        status_changed = False
        for couple in meeting[time]:
            if people_status[couple[0]] != people_status[couple[1]]:
                status_changed = True
                people_status[couple[0]] = people_status[couple[1]] = True
        if not status_changed:
            break

# create the list of infected people
infected_people = []
for people_id, status in people_status.items():
    if status:
        infected_people.append(people_id)


print(infected_people)

将打印结果：

[1, 2, 3, 5]