Editorial for SAC '22 Code Challenge 3 P4 - Finding Friends

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

Maintain an adjacency list for all the friendships.

For a type $1$ ~1~ query, start a BFS from $u$ ~u~ and output the distance to $v$ ~v~ (or -1 if it cannot be reached).

For a type $2$ ~2~ query, loop through all the edges in $u$ ~u~ and remove the one connecting it to $v$ ~v~; likewise, loop through all the edges in $v$ ~v~ and remove the one connecting it to $u$ ~u~.

Time Complexity: $\mathcal{O}(QN)$ ~\mathcal{O}(QN)~

Subtask 2

First, realize that if two friends are connected, they have a lowest common ancestor (LCA), so precompute the required values to query for the LCA between two nodes.

Then, reversing the operations (i.e., connecting friendships instead of destroying them by processing the last query first and first query last) allows us to maintain whether friends are connected by using a disjoint-set.

For a type $1$ ~1~ query, if they are in the same component, query the distance between them by determining the LCA of $u$ ~u~ and $v$ ~v~ and then finding the distance from $u$ ~u~ to the LCA and then the LCA to $v$ ~v~; if they are not in the same component, output -1.

For a type $2$ ~2~ query, connect $u$ ~u~ and $v$ ~v~ with the union function of the disjoint-set.

Time Complexity: $\mathcal{O}(Q \log(N) + N \log(N))$ ~\mathcal{O}(Q \log(N) + N \log(N))~

Note that there are many solutions to this problem (including online solutions like link-cut tree).

Comments

There are no comments at the moment.