Number of Groups (Codeforces 1691E)
Tags: Greedy, dsu

You are given $$$n$$$ colored segments on the number line. Each segment is either colored red or blue. The $$$i$$$-th segment can be represented by a tuple $$$(c_i, l_i, r_i)$$$. The segment contains all the points in the range $$$[l_i, r_i]$$$, inclusive, and its color denoted by $$$c_i$$$:   if $$$c_i = 0$$$, it is a red segment;  if $$$c_i = 1$$$, it is a blue segment. We say that two segments of different colors are connected, if they share at least one common point. Two segments belong to the same group, if they are either connected directly, or through a sequence of directly connected segments. Find the number of groups of segments.   

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of segments. Each of the next $$$n$$$ lines contains three integers $$$c_i, l_i, r_i$$$ ($$$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$$$), describing the $$$i$$$-th segment. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single integer $$$k$$$, the number of groups of segments.

Note: In the first example there are $$$5$$$ segments. The segments $$$1$$$ and $$$2$$$ are connected, because they are of different colors and share a point. Also, the segments $$$2$$$ and $$$3$$$ are connected, and so are segments $$$4$$$ and $$$5$$$. Thus, there are two groups: one containing segments $$$\{1, 2, 3\}$$$, and the other one containing segments $$$\{4, 5\}$$$.

Sample Inputs:
2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4

Sample Outputs:
2
3

Solution (Python):
from sys import stdin

def solve_case():
    n = int(stdin.readline())
    segs = [tuple(map(int, stdin.readline().split())) + (i,) for i in range(n)]
    segs.sort(key=lambda x: x[1])
    par = [-1] * n
    cnt_comp = n

    def find_set(u):
        p = u
        while par[p] >= 0:
            p = par[p]
        while u != p:
            t = par[u]
            par[u] = p
            u = t
        return p

    def join(u, v):
        nonlocal cnt_comp
        nonlocal par
        u = find_set(u)
        v = find_set(v)
        if u == v:
            return
        if -par[u] < -par[v]:
            (u, v) = (v, u)
        par[u] += par[v]
        par[v] = u
        cnt_comp -= 1
    hp = [[], []]
    for (col, l, r, id) in segs:
        for elm in hp[1 - col]:
            if elm[0] < l:
                continue
            join(elm[1], id)
        if len(hp[1 - col]):
            hp[1 - col] = [max(hp[1 - col])]
        hp[col].append((r, id))
    return cnt_comp
for testcase in range(int(stdin.readline())):
    print(solve_case())

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

class unionfind:

    def __init__(self, uni_num):
        self.uni_num = uni_num
        self.union_root = [-1 for i in range(self.uni_num + 1)]
        self.union_depth = [0] * (self.uni_num + 1)
        self.e_num = [0] * (self.uni_num + 1)

    def find(self, x):
        if self.union_root[x] < 0:
            return x
        else:
            self.union_root[x] = self.find(self.union_root[x])
            return self.union_root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            self.e_num[x] += 1
            return
        if self.union_depth[x] < self.union_depth[y]:
            (x, y) = (y, x)
        if self.union_depth[x] == self.union_depth[y]:
            self.union_depth[x] += 1
        self.union_root[x] += self.union_root[y]
        self.union_root[y] = x
        self.e_num[x] += self.e_num[y] + 1

    def size(self, x):
        return -self.union_root[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def edge(self, x):
        return self.e_num[self.find(x)]
T = int(input())
for iii in range(T):
    n = int(input())
    nod = []
    only0 = []
    only1 = []
    for i in range(n):
        (c, l, r) = map(int, input().split())
        nod.append((c, l, r))
    nod.sort(key=lambda x: x[2])
    stack = []
    uf = unionfind(n)
    for i in range(n):
        (c, l, r) = nod[i]
        if c == 0:
            ind0 = r
            ind1 = -1
            while stack and stack[-1][1] >= l:
                (p0, p1, bf) = stack.pop()
                uf.unite(i, bf)
                ind1 = max(ind1, p1)
            while only1 and only1[-1][1] >= l:
                (p0, p1, bf) = only1.pop()
                uf.unite(i, bf)
                ind1 = max(ind1, p1)
            if ind1 == -1:
                only0.append((ind0, ind1, i))
            else:
                stack.append((ind0, ind1, i))
        else:
            ind0 = -1
            ind1 = r
            while stack and stack[-1][0] >= l:
                (p0, p1, bf) = stack.pop()
                uf.unite(i, bf)
                ind0 = max(ind0, p0)
            while only0 and only0[-1][0] >= l:
                (p0, p1, bf) = only0.pop()
                uf.unite(i, bf)
                ind0 = max(ind0, p0)
            if ind0 == -1:
                only1.append((ind0, ind1, i))
            else:
                stack.append((ind0, ind1, i))
    ans = 0
    for i in range(n):
        if i == uf.find(i):
            ans += 1
    print(ans)

Solution (Python):
from collections import deque
tc = int(input())
for t in range(tc):
    n = int(input())
    red = []
    blue = []
    for j in range(n):
        (c, s, f) = map(int, input().split())
        if c == 0:
            red.append([s, f, 'r'])
        else:
            blue.append([s, f, 'b'])
    red.sort(reverse=True)
    blue.sort(reverse=True)
    stck = deque()
    coun = 0
    while 1:
        if len(stck) == 0 and blue and red:
            coun = coun + 1
            if red[-1][1] <= blue[-1][1]:
                stck.append(red.pop())
            else:
                stck.append(blue.pop())
        elif len(stck) == 0 and (len(blue) == 0 or len(red) == 0):
            if len(blue) == 0:
                coun = coun + len(red)
                break
            else:
                coun = coun + len(blue)
                break
        q = stck.popleft()
        if q[-1] == 'r':
            while blue and blue[-1][0] <= q[1]:
                if blue[-1][1] < q[0]:
                    blue.pop()
                    coun += 1
                    continue
                stck.append(blue.pop())
        else:
            while red and red[-1][0] <= q[1]:
                if red[-1][1] < q[0]:
                    red.pop()
                    coun += 1
                    continue
                stck.append(red.pop())
    print(coun)