Submit Info #2628

Problem Lang User Status Time Memory
Unionfind python3 renoyu AC 642 ms 44.70 MiB

ケース詳細
Name Status Time Memory
example_00 AC 21 ms 4.04 MiB
random_00 AC 516 ms 24.86 MiB
random_01 AC 526 ms 25.72 MiB
random_02 AC 359 ms 14.42 MiB
random_03 AC 183 ms 25.32 MiB
random_04 AC 265 ms 7.02 MiB
random_05 AC 423 ms 14.41 MiB
random_06 AC 452 ms 44.70 MiB
random_07 AC 114 ms 24.37 MiB
random_08 AC 141 ms 5.84 MiB
random_09 AC 642 ms 24.37 MiB

import sys,collections as cl,bisect as bs sys.setrecursionlimit(100000) input = sys.stdin.readline mod = 10**9+7 Max = sys.maxsize def l(): #intのlist return list(map(int,input().split())) def m(): #複数文字 return map(int,input().split()) def onem(): #Nとかの取得 return int(input()) def s(x): #圧縮 a = [] aa = x[0] su = 1 for i in range(len(x)-1): if aa != x[i+1]: a.append([aa,su]) aa = x[i+1] su = 1 else: su += 1 a.append([aa,su]) return a def jo(x): #listをスペースごとに分ける return " ".join(map(str,x)) def max2(x): #他のときもどうように作成可能 return max(map(max,x)) def In(x,a): #aがリスト(sorted) k = bs.bisect_left(a,x) if k != len(a) and a[k] == x: return True else: return False """ def nibu(x,n,r): ll = 0 rr = r while True: mid = (ll+rr)//2 if rr == mid: return ll if (ここに評価入れる): rr = mid else: ll = mid+1 """ import collections import itertools import operator class UnionFind: def __init__(self, x): class KeyDict(dict): def __missing__(self, key): self[key] = key return key self.parent = KeyDict() self.rank = collections.defaultdict(int) self.size = collections.defaultdict(lambda: 1) if x is not None: for elem in range(x+1): _, _, _ = self.parent[elem], self.rank[elem],self.size[elem] def find(self, x): if self.parent[x] == x: return x else: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def unite(self, x, y): x = self.find(x) y = self.find(y) if not self.are_same(x,y): xx = self.size[x] yy = self.size[y] if self.rank[x] < self.rank[y]: self.parent[x] = y self.size[y] += xx else: self.parent[y] = x self.size[x] += yy if self.rank[x] == self.rank[y]: self.rank[x] += 1 def Size(self,x): return self.size[self.find(x)] def are_same(self, x, y): '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))''' return self.find(x) == self.find(y) def grouper(self): roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()] root = operator.itemgetter(1) for _, group in itertools.groupby(sorted(roots, key=root), root): yield [x for x, _ in group] N,M = m() un = UnionFind(N) for i in range(M): a,b,c = m() if a == 0: un.unite(b,c) else: if un.are_same(b,c): print(1) else: print(0)