Infected People finding Algorithm

Question

I have a algorithm that solves for 'affected people' in given input. I have to solve the list of people who are affected. People are denoted by numbers, and two people interact with each other at given time N. If either of the person is affected, the other becomes affected too.

First, N(number of people) and M(total interactions) are given. and then (P1 P2 time) are given across M lines.

For example, 5 5

2 3 1

1 2 2

3 4 2

1 3 3

2 5 4

is given.

This means that there are 5 people, who have 5 interactions, which followed by 5 lines denoting person 2 and 3 meeting at time 1, 1 and 2 meeting at time 2, 3 and 4 meeting at time 2, and so on.(times may not be ordered).

At the start, person 1 is always infected.

So at time 2, person 1 and 2 meets, making person 2 infected, person 1 and 3 meets at time 3, making person 3 infected, and finally, person 2 and 5 meets at time 4, making person 5 infected.

This makes person 1, 2, 3, 5 infected at the end.

Interactions happen by time, and multiple interactions can happen simultaneously, and if that is the case, most people have to be considered to be affected.

For Example, if person 1 and 3 is infected, and (4 6 3) (3 6 3) is given as inputs, (3 6 3) has to be calculated first to get person 6 infected and person 4 infected as well.

To solve this question, I created this algorithm, and it has terrible running time, and I need help optimizing this algorithm.

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)]))

I'm very new at stack overflow, and I'm not used to the formatting and the posting guidelines, so I'm sorry if I'm wrong. And thank you in advance.

user_3308055 · Answer

Pseudocode:

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

user_10291310 · Answer

Yet another way of how one can approach this problem would be by using the union-find algorithm which will have a runtime complexity of O(n*log(n)). The idea is pretty straight forward:

Sort the give input based on the time parameter in the ascending order.
Group the interactions by time and for every group, iterate over the interactions and union the people involved in the same.
In the union operation persist the information if the formulated group is infected (see code for better understanding).
For every person involved in the interaction in this group, check if he belongs to an infected group and mark him as infected as well.
Reset the union-find state for the persons involved in this group back to original so that we can proceed to process the other group afresh while maintaining information about the currently infected people.

Here's the code for the same:

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]]))

user_5661651 · Answer

See comment in code:

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)

will print the result:

[1, 2, 3, 5]

Infected People finding Algorithm

3 Answers