CF 1029534 - School Contact Tracing

Rating: -
Tags: -
Solve time: 44s
Verified: yes

Solution

Problem Understanding

We are given a group of students and a log of encounters between pairs of them. Some students are initially infected, and whenever an infected student has been recorded as meeting another student, the infection spreads through that contact relationship. After processing all recorded encounters, we need to determine which students end up infected.

A useful way to rephrase the input is to think of students as nodes in a graph and each recorded encounter as an undirected edge. Infection does not depend on timing or direction beyond the fact that contact connects two students. Once a student becomes infected, every student reachable through a chain of contacts also becomes infected.

The output is typically the final set or count of infected students after this propagation stabilizes, meaning no new infections are possible.

From a constraints perspective, the structure strongly suggests up to around $10^5$ students and contacts. Any approach that attempts repeated graph traversals per infected node would degrade to quadratic behavior in dense cases, since infection can cascade through large connected components. This pushes us toward a near-linear solution, ideally $O(n + m)$ or $O(m \alpha(n))$.

A few edge cases matter here. If no student is initially infected, the answer must remain empty regardless of contacts, since there is no source of propagation. If all students are initially infected, every student remains infected even if there are no contacts. Another subtle case arises when the contact list is empty but initial infections exist; in that case, only the initial set is reported, since there is no propagation path.

Approaches

A direct simulation would repeatedly scan all contacts and spread infection in rounds. In each round, we would check every edge and mark new infections if one endpoint is infected. This is correct because infection only travels along edges and can only expand outward. However, in the worst case, infection may propagate across a chain of length $m$, and each round scans all $m$ edges, producing $O(nm)$ behavior. With $m$ near $10^5$, this quickly becomes infeasible.

The key observation is that infection depends only on connectivity, not order of encounters. Once two students are connected by any sequence of contacts, infection can travel between them regardless of sequence in time. This reduces the problem to finding connected components in an undirected graph and then marking any component that contains at least one initially infected node as fully infected.

This structure is exactly what a Disjoint Set Union (DSU) or Union-Find structure captures efficiently. We merge students whenever a contact is recorded, and afterward we check which components contain infected sources.

Approach	Time Complexity	Space Complexity	Verdict
Simulation (multi-pass BFS over edges)	$O(nm)$	$O(n + m)$	Too slow
DSU / Connected Components	$O(m \alpha(n))$	$O(n)$	Accepted

Algorithm Walkthrough

Initialize a DSU structure where each student starts in their own component. This represents that initially no contacts are known, so each node is isolated.
Read all contact pairs and union their endpoints in the DSU. Each union merges two components because a direct encounter guarantees connectivity between them.
Maintain a boolean array indicating which students are initially infected.
After all unions are complete, for each student, determine the representative of their DSU component. Mark that component as infected if any student in it is infected.
Finally, iterate through all students and output those whose component is marked infected.

The reason we defer infection propagation until after all unions is that DSU encodes connectivity independent of processing order. If we tried to propagate infection during union operations, we would still end up needing to maintain component-level state, which is simpler to compute in a final pass.

Why it works

The DSU partitions students into equivalence classes where each class corresponds to a connected component in the contact graph. Infection is monotonic along edges: once one node in a component is infected, every node in that component is reachable and therefore infected. This creates a direct equivalence between “infected students” and “components containing at least one initially infected node,” ensuring correctness.

Python Solution

import sys
input = sys.stdin.readline

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]

def solve():
    n, m = map(int, input().split())
    infected_count = int(input())
    infected = list(map(int, input().split())) if infected_count else []

    infected = [x - 1 for x in infected]

    dsu = DSU(n)

    for _ in range(m):
        u, v = map(int, input().split())
        dsu.union(u - 1, v - 1)

    infected_root = set()
    for x in infected:
        infected_root.add(dsu.find(x))

    res = []
    for i in range(n):
        if dsu.find(i) in infected_root:
            res.append(str(i + 1))

    print(" ".join(res))

if __name__ == "__main__":
    solve()

The DSU implementation uses path compression and union by size to ensure near-constant amortized complexity per operation. The union step builds connectivity incrementally from the contact list. After that, the infected set is mapped into component representatives so that infection becomes a property of a whole component rather than individual nodes.

The final scan checks membership in infected components. This avoids any repeated graph traversal and ensures each node is processed a constant number of times.

Worked Examples

Example 1

Assume 5 students, contacts: (1,2), (2,3), (4,5), and initially infected student 1.

After processing unions, we get components {1,2,3} and {4,5}. Infection starts in component {1,2,3}, so all students in that component become infected.

Step	Operation	DSU Components	Infected Roots
1	init	{1}{2}{3}{4}{5}	{1}
2	union(1,2)	{1,2}{3}{4}{5}	{1}
3	union(2,3)	{1,2,3}{4}{5}	{1}
4	union(4,5)	{1,2,3}{4,5}	{1}
5	mark infection	same	{1,2,3} component

Output is 1 2 3.

This confirms that infection follows connectivity, not direct adjacency alone.

Example 2

Consider 4 students, contacts (1,2), (3,4), and initially infected students 1 and 3.

We get two disconnected components, each with an infected source.

Step	Operation	DSU Components	Infected Roots
1	init	{1}{2}{3}{4}	{1,3}
2	union(1,2)	{1,2}{3}{4}	{1,3}
3	union(3,4)	{1,2}{3,4}	{1,3}

Both components are infected, so all students are infected.

Output is 1 2 3 4.

This shows that multiple disconnected outbreaks are handled independently but uniformly.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(m \alpha(n) + n \alpha(n))$	Each union/find is nearly constant due to path compression
Space	$O(n)$	DSU arrays and infected tracking

The structure fits comfortably within typical constraints up to $10^5$ nodes and edges because DSU operations scale almost linearly in practice.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    return solve() if False else ""  # placeholder if embedding externally

# Since we cannot import solve cleanly in this format, we instead show asserts conceptually:

# custom cases
# single node infected
# assert run("1 0\n1\n1\n") == "1"

# no infection
# assert run("3 2\n0\n\n1 2\n2 3\n") == ""

# full chain infection
# assert run("4 3\n1\n1\n1 2\n2 3\n3 4\n") == "1 2 3 4"

Test input	Expected output	What it validates
single node infected	`1`	minimal case
no initial infection	empty	propagation absence
chain graph	all nodes	transitive closure

Edge Cases

A key edge case is when infection starts but there are no contacts. For example, if student 2 is infected in a 3-student system with zero edges, DSU remains with isolated nodes. The infected root set contains only the representative of student 2, and no unions modify this. The output correctly lists only student 2.

Another case is when all students are initially infected but the graph is disconnected. DSU still produces multiple components, but every component already contains infection, so every node is marked infected regardless of structure. This confirms that the algorithm does not incorrectly depend on connectivity to create infections, only to propagate them.