Learning Languages

Reframing the problem

Build a graph on employees.

• Each employee is a vertex.
• Put an edge between employees $i$ and $j$ if they share at least one language.

Then two employees can correspond iff they are in the same connected component of this graph, because translators can relay the message along a path. So the whole problem is really about merging connected components. Cute disguise, but it is just components wearing a fake mustache.

What can one lesson do?

Suppose employee $u$ learns language $\ell$.

There are only two possibilities:

• Nobody knew $\ell$ before. Then this lesson connects nothing.
• Some employees already knew $\ell$. Then $u$'s entire current component merges with the component containing language $\ell$.

And that is all.

Why can one lesson merge with at most one other component? Because after we build the initial graph, every language belongs to exactly one connected component. If language $\ell$ were known in two different components, those components would already be connected through employees knowing $\ell$. Contradiction.

So each lesson decreases the number of employee-components by at most $1$.

The formula

Let:

• $c$ = number of connected components of the employee graph,
• $S = \sum_{i=1}^{n} k_i$ = total number of initially known languages across all employees.

Then the answer is

$$\text{ans} = \begin{cases} n, & S = 0, \\ c - 1, & S > 0. \end{cases}$$

Why $c-1$ when $S > 0$?

Lower bound: Each lesson reduces the number of connected components by at most $1$. To go from $c$ components down to $1$, we need at least

$$c - 1$$

lessons.

Upper bound: Pick any component that contains at least one known language. Use it as a hub. For every other component, choose one employee in that component and teach them any language known in the hub. That single lesson merges the entire component into the hub.

That uses exactly one lesson per extra component, so total cost is

$$c - 1.$$

Lower bound matches upper bound, so done.

Why $n$ when $S = 0$?

This is the only trap in the problem.

If nobody knows any language initially, then the first lesson cannot connect two employees; it only gives one person some language. So after the first lesson, the number of connected components is still $n$.

From then on, each additional lesson can reduce the number of components by at most $1$, so we need at least

$$1 + (n-1) = n$$

lessons in total.

And $n$ is achievable: just teach the same language to all $n$ employees.

So the all-zero case is exactly $n$, not $n-1$. That off-by-one has killed many perfectly decent submissions. Brutal.

How to compute $c$

Use DSU on employees.

For each language $\ell$, store the first employee who knows it.

When employee $i$ knows language $\ell$:

• if nobody has claimed $\ell$ yet, set first[\ell] = i;
• otherwise union employee $i$ with first[\ell].

Why does this work? Because all employees knowing the same language must belong to the same connected component, and DSU handles transitivity for free.

Employees with $0$ languages simply stay isolated in the DSU, which is exactly what we want.

Correctness sketch

1. The DSU builds exactly the connected components of the initial communication graph.
2. One paid lesson can decrease the number of employee-components by at most $1$.
3. Therefore, if $S > 0$, at least $c-1$ lessons are necessary.
4. If $S > 0$, the hub construction uses exactly $c-1$ lessons, so it is optimal.
5. If $S = 0$, the first lesson cannot connect anything, so the minimum becomes $n$.

Therefore the formula above is correct.

Complexity

Let

$$K = \sum_{i=1}^{n} k_i.$$

The DSU operations take

$$O(K \alpha(n)),$$

which is basically linear for any sane universe.

Memory usage is

$$O(n + m).$$