結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2022-12-12 23:33:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 837 ms / 2,000 ms |
コード長 | 3,113 bytes |
コンパイル時間 | 596 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 242,432 KB |
最終ジャッジ日時 | 2024-11-06 21:15:58 |
合計ジャッジ時間 | 32,922 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
from collections import defaultdictfrom typing import Listimport syssys.setrecursionlimit(10**8)import pypyjitpypyjit.set_param("max_unroll_recursion=-1")input = sys.stdin.readlineclass UnionFind:"""0-indexed"""def __init__(self, n):self.n = nself.parent = [-1] * nself.__group_count = ndef unite(self, x, y) -> bool:"""xとyをマージ"""x = self.root(x)y = self.root(y)if x == y:return Falseself.__group_count -= 1if self.parent[x] > self.parent[y]:x, y = y, xself.parent[x] += self.parent[y]self.parent[y] = xreturn Truedef is_same(self, x, y) -> bool:"""xとyが同じ連結成分か判定"""return self.root(x) == self.root(y)def root(self, x) -> int:"""xの根を取得"""if self.parent[x] < 0:return xelse:# 経路圧縮あり# self.parent[x] = self.root(self.parent[x])# return self.parent[x]# 経路圧縮なしreturn self.root(self.parent[x])def size(self, x) -> int:"""xが属する連結成分のサイズを取得"""return -self.parent[self.root(x)]def all_sizes(self) -> List[int]:"""全連結成分のサイズのリストを取得 O(N)"""sizes = []for i in range(self.n):size = self.parent[i]if size < 0:sizes.append(-size)return sizesdef members(self, x) -> List[int]:"""xが属するグループのリストを返す O(N)"""mem = []r = self.root(x)for i in range(self.n):if self.root(i) == r:mem.append(i)return memdef groups(self) -> List[List[int]]:"""全連結成分の内容のリストを取得 O(N・α(N))"""groups = dict()for i in range(self.n):p = self.root(i)if not groups.get(p):groups[p] = []groups[p].append(i)return list(groups.values())@propertydef group_count(self) -> int:"""連結成分の数を取得 O(1)"""return self.__group_countN = int(input())uf = UnionFind(N)G = [list() for _ in range(N)]def dfs(v,p,start,f,edge):if v==start and f==True:return Trueelif v==start:f = Trueif len(G[v])==1:return Falsefor nex in G[v]:if nex==p:continueif dfs(nex,v,start,f,edge):edge.append((nex,v))return Trued = defaultdict(int)for i in range(N):a, b = map(int, input().split())a-=1;b-=1G[a].append(b)G[b].append(a)d[str(a)+'_'+str(b)] = i+1d[str(b)+'_'+str(a)] = i+1if uf.is_same(a,b):edge = []dfs(a,b,a,False,edge)print(len(edge))ans = []for u,v in edge:ans.append(d[str(u)+'_'+str(v)])ans.sort()print(*ans)else:uf.unite(a,b)