class Graph: __slots__=("edge_number", "adjacent") #入力定義 def __init__(self, N=0): """ N 頂点の空グラフ (多重辺なし) を生成する.""" self.edge_number=0 self.adjacent=[set() for _ in range(N)] #頂点の追加 def add_vertex(self): """ 頂点を追加する. """ self.adjacent.append(set()) return self.order()-1 def add_vertices(self, k): """ 頂点を k 個追加する. k: int """ n=self.order() self.adjacent.extend([set() for _ in range(k)]) return list(range(n,n+k)) #辺の追加 def add_edge(self,u,v): """ 無向辺 uv を加える""" if not self.edge_exist(u,v): self.adjacent[u].add(v) self.adjacent[v].add(u) self.edge_number+=1 return self.edge_number-1 else: return -1 #辺を除く def remove_edge(self,u,v): """ 無向辺 uv が存在するならば除く""" if self.edge_exist(u,v): self.adjacent[u].discard(v) self.adjacent[v].discard(u) self.edge_number-=1 return True else: return False def reset_vertex(self, u): """ 頂点 u に接続している辺を全て消す.""" X=self.adjacent[u].copy() for v in X: self.remove_edge(u,v) #Walkの追加 def add_walk(self,*walk): """ walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える.""" n=len(walk) for i in range(n-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 が存在するか? """ return v in self.adjacent[u] #近傍 def neighbohood(self,v): """ 頂点 v の近傍を求める. """ return self.adjacent[v] #次数 def degree(self,v): """ 頂点 v の次数を求める. """ if v in self.adjacent[v]: return len(self.adjacent[v])+1 else: return len(self.adjacent[v]) #頂点数 def vertex_count(self): """ グラフの頂点数 (位数) を出力する. """ return len(self.adjacent) def order(self): """ グラフの位数 (頂点数) を出力する. """ return len(self.adjacent) #辺数 def edge_count(self): """ 辺の本数 (サイズ) を出力する.""" return self.edge_number def size(self): """ サイズ (辺の本数) を出力する. """ return self.edge_number #頂点vを含む連結成分 def connected_component(self,v): """ 頂点 v を含む連結成分を出力する.""" from collections import deque T=[0]*self.N; T[v]=1 Q=deque([v]) while Q: u=Q.popleft() for w in self.adjacent[u]: if T[w]==0: T[w]=1 Q.append(w) return [x for x in range(self.N) if T[x]] #距離 def distance(self,u,v): """ 2頂点 u,v 間の距離を求める.""" if u==v: return 0 from collections import deque inf=float("inf") T=[inf]*self.N; T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) if x==v: return T[x] return inf #ある1点からの距離 def distance_all(self,u): """ 頂点 u からの距離を求める.""" from collections import deque inf=float("inf") T=[inf]*self.N; T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) return T #最短路 def shortest_path(self,u,v): """ u から v への最短路を求める (存在しない場合は None). """ if u==v: return [u] from collections import deque inf=float("inf") T=[-1]*self.N Q=deque([u]); T[u]=u while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==-1: T[x]=w Q.append(x) if x==v: P=[v] a=v while a!=u: a=T[a] P.append(a) return P[::-1] return None def edge_yielder(self): g=self.adjacent for v in range(self.vertex_count()): for w in g[v]: if v