Unusual Minesweeper (Codeforces 1619G)
Tags: Greedy, dsu

Polycarp is very fond of playing the game Minesweeper. Recently he found a similar game and there are such rules.There are mines on the field, for each the coordinates of its location are known ($$$x_i, y_i$$$). Each mine has a lifetime in seconds, after which it will explode. After the explosion, the mine also detonates all mines vertically and horizontally at a distance of $$$k$$$ (two perpendicular lines). As a result, we get an explosion on the field in the form of a "plus" symbol ('+'). Thus, one explosion can cause new explosions, and so on.Also, Polycarp can detonate anyone mine every second, starting from zero seconds. After that, a chain reaction of explosions also takes place. Mines explode instantly and also instantly detonate other mines according to the rules described above.Polycarp wants to set a new record and asks you to help him calculate in what minimum number of seconds all mines can be detonated.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.An empty line is written in front of each test suite.Next comes a line that contains integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — the number of mines and the distance that hit by mines during the explosion, respectively.Then $$$n$$$ lines follow, the $$$i$$$-th of which describes the $$$x$$$ and $$$y$$$ coordinates of the $$$i$$$-th mine and the time until its explosion ($$$-10^9 \le x, y \le 10^9$$$, $$$0 \le timer \le 10^9$$$). It is guaranteed that all mines have different coordinates.It is guaranteed that the sum of the values $$$n$$$ over all test cases in the test does not exceed $$$2 \cdot 10^5$$$.

Output: Print $$$t$$$ lines, each of the lines must contain the answer to the corresponding set of input data  — the minimum number of seconds it takes to explode all the mines.

Note:   Picture from examples First example:  $$$0$$$ second: we explode a mine at the cell $$$(2, 2)$$$, it does not detonate any other mine since $$$k=0$$$.  $$$1$$$ second: we explode the mine at the cell $$$(0, 1)$$$, and the mine at the cell $$$(0, 0)$$$ explodes itself.  $$$2$$$ second: we explode the mine at the cell $$$(1, 1)$$$, and the mine at the cell $$$(1, 0)$$$ explodes itself.Second example:  $$$0$$$ second: we explode a mine at the cell $$$(2, 2)$$$ we get:     $$$1$$$ second: the mine at coordinate $$$(0, 0)$$$ explodes and since $$$k=2$$$ the explosion detonates mines at the cells $$$(0, 1)$$$ and $$$(1, 0)$$$, and their explosions detonate the mine at the cell $$$(1, 1)$$$ and there are no mines left on the field. 

Sample Inputs:
3

5 0
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

5 2
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

6 1
1 -1 3
0 -1 9
0 1 7
-1 0 1
-1 1 9
-1 -1 7

Sample Outputs:
2
1
0

Solution (Python):
import sys

def read_line():
    return sys.stdin.readline().strip()

def read_ints_line():
    return tuple([int(x) for x in read_line().split()])

def bfs(x, y, t, k, i_by_x, i_by_y, was, i):
    min_t = t[i]
    current_queue = [i]
    was[i] = True
    while len(current_queue) > 0:
        next_queue = []
        for i in current_queue:
            min_t = min(min_t, t[i])
            for next_i in i_by_x[x[i]]:
                if y[i] - k <= y[next_i] <= y[i] + k and (not was[next_i]):
                    next_queue.append(next_i)
                    was[next_i] = True
            for next_i in i_by_y[y[i]]:
                if x[i] - k <= x[next_i] <= x[i] + k and (not was[next_i]):
                    next_queue.append(next_i)
                    was[next_i] = True
        current_queue = next_queue
    return min_t
t = int(read_line())
for _ in range(t):
    read_line()
    (n, k) = read_ints_line()
    x = [0] * n
    y = [0] * n
    t = [0] * n
    for i in range(n):
        (x[i], y[i], t[i]) = read_ints_line()
    i_by_x = {}
    i_by_y = {}
    for i in range(n):
        if x[i] not in i_by_x:
            i_by_x[x[i]] = []
        if y[i] not in i_by_y:
            i_by_y[y[i]] = []
        i_by_x[x[i]].append(i)
        i_by_y[y[i]].append(i)
    was = [False] * n
    time_to_kill = []
    for i in range(n):
        if not was[i]:
            time_to_kill.append(bfs(x, y, t, k, i_by_x, i_by_y, was, i))
    time_to_kill.sort(reverse=True)
    for i in range(len(time_to_kill)):
        time_to_kill[i] = min(i, time_to_kill[i])
    print(f'{max(time_to_kill)}')

Solution (Python):
import sys
Z = sys.stdin.readline
Y = lambda : map(int, Z().split())
X = range
from collections import defaultdict as D

class U:

    def __init__(self, n):
        self.p = [*X(n)]

    def f(self, a):
        b = a
        while a != self.p[a]:
            a = self.p[a]
        while b != a:
            (self.p[b], b) = (a, self.p[b])
        return a
O = []
N = 10 ** 10
for _ in X(int(Z())):
    Z()
    (n, k) = Y()
    G = D(list)
    a = []
    u = U(n)
    b = []
    for i in X(n):
        (x, y, t) = Y()
        a.append(t)
        G[x].append((y, i))
        G[y + N].append((x, i))
    for x in G:
        g = G[x]
        L = len(g)
        g.sort()
        if L > 1:
            for i in X(1, L):
                v = u.f(g[i - 1][1])
                w = u.f(g[i][1])
                if v != w and g[i][0] - g[i - 1][0] <= k:
                    u.p[w] = v
                    a[v] = min(a[v], a[w])
                    a[w] = N
    b = sorted((i for i in a if i < N))
    c = 0
    while c < len(b) - 1 and b[-2 - c] > c:
        c += 1
    print(c)

Solution (Python):
import sys
Z = sys.stdin.readline
Y = lambda : map(int, Z().split())
X = range
from collections import defaultdict as D

class U:

    def __init__(self, n):
        self.p = [*X(n)]

    def f(self, a):
        b = a
        while a != self.p[a]:
            a = self.p[a]
        while b != a:
            (self.p[b], b) = (a, self.p[b])
        return a
O = []
N = 10 ** 10
for _ in X(int(Z())):
    Z()
    (n, k) = Y()
    G = D(list)
    a = []
    u = U(n)
    b = []
    for i in X(n):
        (x, y, t) = Y()
        a.append(t)
        G[x].append((y, i))
        G[y + N].append((x, i))
    for x in G:
        g = G[x]
        L = len(g)
        g.sort()
        if L > 1:
            for i in X(1, L):
                v = u.f(g[i - 1][1])
                w = u.f(g[i][1])
                if v != w and g[i][0] - g[i - 1][0] <= k:
                    u.p[w] = v
                    a[v] = min(a[v], a[w])
                    a[w] = N
    b = sorted((i for i in a if i < N))
    c = 0
    while c < len(b) - 1 and b[-2 - c] > c:
        c += 1
    print(c)