Editorial for Friends Two

Use this editorial only when stuck, and do not 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$ query, unite $a$ and $b$ ; on a reversed type- $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)$ with union by size and path compression.

Solution (Python)

Code 1

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)

Comments0

No comments yet

Be the first to comment.

Editorial for Friends Two

Approach

Solution (Python)

Comments0

New comment