Official Analysis (Java)

Editorial

Since removing edges via DSU is not feasible, we need a way to process the queries such that we only ever join nodes.

We can sort the queries from greatest to least weight to process them offline. In a similar manner, we sort the edges based on the same order.

At each query, we can add every edge with a weight greater than or equal to the current query's weight.

We return the size of the connected component minus one for the number of videos that will be recommended from the queried one.

Implementation

Copy
#include <bits/stdc++.h>

using namespace std;

struct DSU {
	vector<int> e;
	void init(int n) { e = vector<int>(n, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); };
	bool sameSet(int x, int y) { return get(x) == get(y); };
	int size(int x) { return -e[get(x)]; }