Editorial for Friends Two

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.

Approach

Friendships only disappear, never appear, so process the queries offline in reverse.

At the end of the year there are no friendships. Reading the log backwards, each breakup 1 a b becomes the restoration of that edge. Maintain a DSU: on a reversed type- $1$ ~1~ query, unite $a$ ~a~ and $b$ ~b~; on a reversed type- $2$ ~2~ query, answer whether they are in the same component. Finally reverse the collected answers so they match the original order.

This is $O(n + q)$ ~O(n + q)~ with union by size and path compression.

Solution (Python)

class DisjointSet():

    def __init__(self,size : int) -> None:
        self.parent = [i for i in range(size)]
        self.size = list[int](1 for _ in range(size))

    def find_set(self,v : int) -> int:

        if (self.parent[v] == v): return v

        parent = self.find_set(self.parent[v])
        self.parent[v] = parent
        return parent

    def union(self,v : int, u : int) -> None:

        a = self.find_set(v)
        b = self.find_set(u)

        if a == b: return

        if (self.size[a] > self.size[b] ): a,b = b,a

        self.parent[a] = b
        self.size[b] += self.size[a]

n,q = (int(x) for x in input().split())

dsu = DisjointSet(n+1)

qs = list[tuple[int,int,int]]()

for _ in range(q):
    qs.append(int(x) for x in input().split())

ans = []

for t,a,b in reversed(qs):
    if t == 1:
        dsu.union(a,b)
    else:
        ans.append("Yes" if dsu.find_set(a) == dsu.find_set(b) else "No")

for a in reversed(ans):
    print(a)

Comments

There are no comments at the moment.