結果
| 問題 | No.1254 補強への架け橋 |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2024-02-12 10:57:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 491 ms / 2,000 ms |
| コード長 | 8,571 bytes |
| コンパイル時間 | 258 ms |
| コンパイル使用メモリ | 82,540 KB |
| 実行使用メモリ | 130,804 KB |
| 最終ジャッジ日時 | 2024-09-28 17:54:24 |
| 合計ジャッジ時間 | 28,918 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 123 |
ソースコード
class Graph:__slots__=("edge_offset", "edge_alive", "edge_ids", "vertex_alive", "adjacent", "deg")#入力定義def __init__(self, N = 0, edge_offset = 0):""" N 頂点の空グラフ (多重辺なし) を生成する."""self.adjacent = [[] for _ in range(N)]self.edge_ids = [[] for _ in range(N)]self.vertex_alive = [1] * Nself.edge_offset = edge_offsetself.edge_alive = [0] * edge_offsetself.deg = [0] * N#頂点の追加def add_vertex(self):""" 頂点を追加する."""self.adjacent.append([])self.edge_ids.append([])self.vertex_alive.append(1)self.deg.append(0)return self.order() - 1def add_vertices(self, k):""" 頂点を k 個追加する.k: int"""n=self.order()self.adjacent.extend([[] for _ in range(k)])self.edge_ids.extend([[] for _ in range(k)])self.vertex_alive.extend([1] * k)self.deg.extend([0] * k)return list(range(n, n + k))#辺の追加def add_edge(self, u, v):""" 無向辺 uv を加える"""j = len(self.edge_alive)self.adjacent[u].append(v)self.adjacent[v].append(u)self.edge_ids[u].append(j)self.edge_ids[v].append(j)self.deg[u] += 1; self.deg[v] += 1self.edge_alive.append(1)return j#辺を除くdef remove_edge(self,u,v):""" 無向辺 uv が存在するならば除く"""passdef reset_vertex(self, u):""" 頂点 u に接続している辺を全て消す."""pass#Walkの追加def add_walk(self, *walk):""" walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える."""for i in range(len(walk) - 1):self.add_edge(walk[i], walk[i + 1])#Cycleの追加def add_cycle(self, *cycle):""" cycle=(c[0], ..., c[n-1]) を加える. """self.add_walk(*cycle)self.add_edge(cycle[-1], cycle[0])#グラフに辺が存在するか否かdef edge_exist(self, u, v):""" 辺 uv が存在するか? """passdef partner(self, v):adj = self.adjacent[v]edge_ids = self.edge_ids[v]return [adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]def partner_with_index(self, v):adj = self.adjacent[v]edge_ids = self.edge_ids[v]return [(adj[k], edge_ids[k]) for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]#近傍def neighborhood(self, v):""" 頂点 v の近傍を求める. """adj = self.adjacent[v]edge_ids = self.edge_ids[v]return list(set(adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]))#次数def degree(self, v):""" 頂点 v の次数を求める. """return self.deg[v]#頂点数def vertex_count(self):""" グラフの頂点数 (位数) を出力する. """return len(self.adjacent)def order(self):""" グラフの位数 (頂点数) を出力する. """return len(self.adjacent)#辺数def edge_count(self):""" 辺の本数 (サイズ) を出力する."""return len(self.edge_alive) - self.edge_offsetdef size(self):""" サイズ (辺の本数) を出力する. """return len(self.edge_alive) - self.edge_offset#頂点vを含む連結成分def connected_component(self, v):""" 頂点 v を含む連結成分を出力する."""N = self.order()stack = [v]comp = [0] * N; comp[v] = 1while stack:x = stack.pop()for y in self.neighborhood(x):if comp[y] == 0:comp[y] = 1stack.append(y)return [x for x in range(N) if comp[x]]#距離def distance(self, u, v, default):""" 2頂点 u,v 間の距離を求める."""if u == v:return 0from collections import dequeN = self.order()dist = [-1] * N; dist[u]=0queue = deque([u])while queue:x = queue.popleft()for y in self.neighborhood(x):if dist[y] == -1:dist[y] = dist[x] + 1queue.append(y)if y == v:return dist[v]return default#ある1点からの距離def distance_all(self,u,default=-1):""" 頂点 u からの距離を求める."""from collections import dequeN = self.order()dist = [-1] * N; dist[u]=0queue = deque([u])while queue:x = queue.popleft()for y in self.neighborhood(x):if dist[y] == -1:dist[y] = dist[x] + 1queue.append(y)return [dist[x] if dist[x] != -1 else default for x in range(N)]#最短路def shortest_path(self, u, v):""" u から v への最短路を求める (存在しない場合は None). """if u == v:return [u]from collections import dequeprev = [-1] * self.order()prev[u] = uqueue = deque([u])while queue:x = queue.popleft()for y in self.adjacent[x]:if prev[x] != -1:continueprev[y] = xqueue.append(y)if y != v:continuepath = [v]a = vwhile a != u:a = prev[a]path.append(a)return path[::-1]return Nonedef edge_yielder(self):u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)for x in range(self.order()):adj = self.adjacent[x]ids = self.edge_ids[x]for k in range(len(adj)):id = ids[k]u[id] = min(x, adj[k])v[id] = max(x, adj[k])for id in range(len(self.edge_alive)):if self.edge_alive[id]:yield (u[id], v[id])def edge_yielder_with_index(self):u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)for x in range(self.order()):adj = self.adjacent[x]ids = self.edge_ids[x]for k in range(len(adj)):id = ids[k]u[id] = min(x, adj[k])v[id] = max(x, adj[k])for id in range(len(self.edge_alive)):if self.edge_alive[id]:yield (id, u[id], v[id])def Lowlink(G: Graph, mode=0):""" G の ord, lowlink を求める.G: Graphoutput: (ord, lowlink)"""from collections import dequeN=G.vertex_count()ord=[-1]*N; low=[-1]*Nflag=[0]*Nadj=G.adjacentparent=[-1]*N#BFSパートfor v in range(N):if flag[v]:continuek=0S=deque([v])T=[]while S:u=S.pop()if flag[u]:continueT.append(u)ord[u]=kk+=1flag[u]=1for w in G.neighborhood(u):if not flag[w]:S.append(w)parent[w]=ufor u in T:low[u]=ord[u]for w in T[:0:-1]:for x in adj[w]:if w==v or x!=parent[w]:low[w]=min(low[w],low[x],ord[x])if mode==0:return ord, lowelse:return ord, low, parent#橋列挙def Bridge(G: Graph):""" G にある橋の id を列挙する.G: Graph"""ord, low = Lowlink(G)return [id for id, u, v in G.edge_yielder_with_index() if (ord[u] < low[v]) or (ord[v] < low[u])]#==================================================def solve():N = int(input())G = Graph(N + 1, 1)for j in range(1, N + 1):u, v = map(int, input().split())G.add_edge(u, v)bridges = set(Bridge(G))anti_bridges = [j for j in range(1, N + 1) if j not in bridges]return f'{len(anti_bridges)}\n{" ".join(map(str, anti_bridges))}'#==================================================import sysinput=sys.stdin.readlinewrite=sys.stdout.writeprint(solve())