結果
問題 |
No.2134 $\sigma$-algebra over Finite Set
|
ユーザー |
👑 ![]() |
提出日時 | 2023-05-11 23:11:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,169 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 85,672 KB |
最終ジャッジ日時 | 2024-11-27 18:55:21 |
合計ジャッジ時間 | 9,390 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 TLE * 1 |
ソースコード
""" https://yukicoder.me/problems/no/2134 """ import sys from sys import stdin def uf_find(n,p): ufl = [] while p[n] != n: ufl.append(n) n = p[n] for i in ufl: p[i] = n return n def uf_union(a,b,p,rank): ap = uf_find(a,p) bp = uf_find(b,p) if ap == bp: return True else: if rank[ap] > rank[bp]: p[bp] = ap elif rank[ap] < rank[bp]: p[ap] = bp else: p[bp] = ap rank[ap] += 1 return False N,M = map(int,stdin.readline().split()) lis = [ [0] * N for i in range(N) ] for loop in range(M): a = list(map(int,stdin.readline().split()))[1:] for i in range(len(a)): a[i] -= 1 a = set(a) b = [] for i in range(N): if i not in a: b.append(i) for i in a: for j in b: lis[i][j] = lis[j][i] = 1 p = [i for i in range(N)] rank = [0] * N for i in range(N): for j in range(i): if lis[i][j] == 0: uf_union(i,j,p,rank) part = 0 for i in range(N): if uf_find(i,p) == i: part += 1 print (pow(2,part,998244353))