leetcode07's blog

By leetcode07, history, 4 years ago, In English

Hello all!

Please help me in solving this problem: CHAIN. Thank you.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

This is a simple DSU question. The general idea is as follows:

In reality, we only need to seriously check the last of the third conditions, as the first 2 are trivial. We will assign each node a value from $$$0 - 2$$$ corresponding to the letters $$$A - C$$$ in the statement. For each query $$$t \; u \; v$$$, we first check whether the nodes are in the same component. If they are, we will simply check whether the given query is true or false with the following rules:

Type 1: $$$val[u] = val[v]$$$
Type 2: $$$(val[u] + 1) \bmod 3 = val[v]$$$

If they are not in the same component, we will have to merge them. For both components, we will already have the relative order of all elements in each component. Then the only thing we need to change is the relationship between $$$u$$$ and $$$v$$$. We check how much we need to change either $$$u$$$ or $$$v$$$ according to the rules above, and we will increment each node in one component by that value. How to choose which component to change? We will always choose the smaller one, since the small-to-large trick will guarantee $$$O(N\log N)$$$, which is our final time complexity.

»
4 years ago, # |
Rev. 4   Vote: I like it -17 Vote: I do not like it

I came up with a solution (got AC):

Imagine the N animals as a network of components. In the network let x eats y be represented by an arrow x -> y. Let d(x, y) be the number of arrows from x to y modulo 3. The distances are taken modulo 3 because in a scenario like this: a -> b -> c -> d, a and d are really the same type.

Maintain an array d where for each animal v, d[v] = d(v, p[v]), where p[v] is the parent of the animal (I did not use path compression). Thus if x and y are in the same component, i.e. find(x) == find(y), answering the query is straightforward, as we can compute d(x, y) = d(x, find(x)) - d(y, find(x)). Finding d(x, find(x)) is easy since we can just walk up the chain starting at x: d(x, find(x)) = d(x, p[x]) + d(p[x], p[p[x]]) + ... + d(p...p[x], find(x)), same for d(y, find(y)).

If x and y are not in the same component, you need to link find(x) to find(y) so that p[find(x)] = find(y) (or vice versa, use the union by size heuristic) and set the value of d(find(x), find(y)) in such a way that d(x, y) = type - 1. You can easily come up with a formula for what d(find(x), find(y)) should be.

The time complexity is $$$O(N + K\text{log}(N))$$$.

Edit: code:

Spoiler