Submission #68761665

---

Source Code Expand

from collections import defaultdict

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n

    def find(self,x): #要素xが属するグループの根を返す
        #根ならその番号を返す
        if self.parents[x]<0: 
            return x 
        # 根でないなら、親の要素で再検索
        else:
            # 走査していく過程で親を書き換える
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y): #要素xが属するグループと要素yが属するグループとを併合する
        #根を探す
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return
        if self.parents[x]>self.parents[y]: #グループの大きい方に合わせる
            x,y=y,x

        self.parents[x]+=self.parents[y] #x(根)の要素にｙ(根)のグループの要素数をプラスする(要素の値は負の数で表される)
        self.parents[y]=x

    def size(self,x): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
    
    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素xが属するグループに属する要素をリストで返す
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    
    def roots(self): #すべての根の要素をリストで返す
        return [i for i ,x in enumerate(self.parents) if x<0]

    def group_count(self): #グループの数を返す
        return len(self.roots())

    def all_group_members(self): #{ルート要素: [そのグループに含まれる要素のリスト], ...}のdefaultdictを返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self): #ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
        return '\n'.join('{}:{}'.format(r,self.members(r)) for r in self.roots())

################################################################################


import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix] 
dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')

N, Q = MI()

uf = UnionFind(N)
cnt_black = [0]*N
B_or_W = [0]*N

ans = []

for _ in range(Q):
    query = LI(-1)
    if query[0] == 0:
        u, v = query[1:]

        if not uf.same(u, v):
            cnt_u = cnt_black[uf.find(u)]
            cnt_v = cnt_black[uf.find(v)]
            uf.union(u, v)

            p = uf.find(u)
            cnt_black[p] = cnt_u + cnt_v
    if query[0] == 1:
        v = query[1]
        if B_or_W[v] == 0:
            B_or_W[v] = 1
            cnt_black[uf.find(v)] += 1
        else:
            B_or_W[v] = 0
            cnt_black[uf.find(v)] -= 1
    if query[0] == 2:
        v = query[1]
        if cnt_black[uf.find(v)] == 0:
            ans.append('No')
        else:
            ans.append('Yes')

pr_line(ans)

Submission Info

Judge Result