Educational Codeforces R#65 (Div. 2) - C. News Distribution
問題概要
グループに所属する数を数えよ
Problem - C - Codeforces
解法
サイズ付きUnionFindを用いる。
が、(10^5) * 5はPythonだと相当きつい。
PyPy3を用いたが、Input関数を止めてsys.stdin.readlineで高速化しない無理だった。。。
提出コード
# coding: UTF-8 import sys def find(x): if node[x] < 0: return x else: node[x] = find(node[x]) return node[x] def unite(x, y): x = find(x) y = find(y) ret = False if x != y: ret = True if rank[x] > rank[y]: node[x] += node[y] node[y] = x else: node[y] += node[x] node[x] = y if rank[x] == rank[y]: rank[y] += 1 return ret def is_same(x, y): return find(x) == find(y) def size(x): return -node[find(x)] readl= lambda: list(map(int, sys.stdin.readline().split())) readt= lambda: tuple(map(int, sys.stdin.readline().split())) read = lambda: sys.stdin.readline().rstrip() readi = lambda: int(read()) readmi = lambda: map(int, sys.stdin.readline().split()) readms = lambda: map(str, sys.stdin.readline().split()) n, m = readmi() node = [-1 for i in range(n + 1)] rank = [0 for _ in range(n + 1)] query = [readt() for _ in range(m)] for a in query: if a[0] >= 2: for j in a[2:]: unite(a[1], j) for i in range(1, n + 1): print(size(i), end=" ")