Knowledge required: complete search or disjoint set

When one has Ebola, everyone in his class can potentially get Ebola. With that observation, we can express each class as a set. When person ~i~ and ~j~ are in the same class, we can simply merge the 2 sets that ~i~ and ~j~ belongs to. Hence, the intended solution to this problem is to use disjoint set to manage the contents of the sets.

The disjoint set data structure has 2 operations ~\operatorname{Find}(a)~ and ~\operatorname{Merge}(a,b)~. When person ~i~ and ~j~ are in the same class, we can simply do ~\operatorname{Merge}(i,j)~. After processing all the classes, we can simply compare the value of ~\operatorname{Find}(1)~ and ~\operatorname{Find}(N)~ to determine if person ~N~ is infected.

A properly implemented disjoint set has a time complexity of ~\mathcal{O}(\alpha(N))~ for each operation, where ~\alpha(N)~ is the Inverse Ackermann function, which is smaller than ~5~ for all reasonable values of ~N~.

Time Complexity: ~\mathcal{O}(N + \sum K_i \alpha(N))~

Alternate solution

Create a vertex for each student and each class. If a student is in a class, then create an edge between that student and that class. In total, there are ~N+M~ vertices and ~\sum K_i~ edges.

Next, do a graph search starting at student ~1~. Make sure to output the visited students. The visited classes can be ignored.

Time Complexity: ~\mathcal{O}(N + \sum K_i)~