(Analysis by Benjamin Qi)

The idea is to process the updates in reverse order and maintain which farms are relevant. Note that once a farm becomes relevant, it never becomes irrelevant due to the assumption that roads are only added between active farms.

For updates of type R, add the $e$-th edge to the graph. If exactly one endpoint of this edge was previously relevant, mark all vertices in the connected component of the other endpoint as relevant as well.

For updates of type D, if vertex $x$ was not previously relevant, then mark every vertex in its connected component as relevant.

For updates of type A, do nothing.

We can process these operations in $O(N+Q)$ time.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;

public class GarbageCollection {

// marks everything in the connected component of a
// as relevant
static void dfs(int a, int time) {
for (int b : adj[a]) {
dfs(b, time);
}
}
}

public static void main(String[] args) throws IOException {
int n = Integer.parseInt(tokenizer.nextToken());
int q = Integer.parseInt(tokenizer.nextToken());
adj = new List[n + 1];
for (int a = 1; a <= n; a++) {
}
answers = new int[n + 1];
Edge[] removed = new Edge[q];
int[] deactivated = new int[q];
Set<Integer> alwaysActive = new HashSet<>();
for (int a = 1; a <= n; a++) {
}
for (int j = 0; j < q; j++) {
char type = tokenizer.nextToken().charAt(0);
if (type == 'D') {
int a = Integer.parseInt(tokenizer.nextToken());
deactivated[j] = a;
alwaysActive.remove(a);
} else if (type == 'A') {
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
} else {
int k = Integer.parseInt(tokenizer.nextToken());
}
}
for (Edge edge : added) {
if (edge != null) {
}
}
for (int a : alwaysActive) {
dfs(a, q);
}
for (int j = q - 1; j > 0; j--) {
if (deactivated[j] != 0) {
dfs(deactivated[j], j);
} else if (removed[j] != null) {
int a = removed[j].from;
int b = removed[j].to;
dfs(a, j);
dfs(b, j);
}
}
}
StringBuilder out = new StringBuilder();
for (int a = 1; a <= n; a++) {
}
System.out.print(out);
}

static class Edge {
final int from;
final int to;

Edge(int from, int to) {
this.from = from;
this.to = to;
}
}
}