import heapq import random from collections import defaultdict,deque class Graph: def __init__(self,V,edges=None,graph=None,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph!=None: self.graph=graph """ self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) """ else: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if bfs_tour: bt=[s] if linked_components: lc=[s] if parents: ps=[None]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bfs_tour: bt.append(y) if linked_components: lc.append(y) if parents: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if uwd[i]==self.inf or uwd[j]==self.inf: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bfs_tour: retu+=(bt,) if bipartite_graph: retu+=(bg,) if linked_components: retu+=(lc,) if parents: retu+=(ps,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def Build_BFSD(self,D): self.bfsd_D=D self.bfsd_L=[[self.V]*(self.bfsd_D+1) for x in range(self.V)] self.bfsd_R=[[0]*(self.bfsd_D+1) for x in range(self.V)] self.bfsd_tour,self.bfsd_parents=self.SIV_BFS(0,bfs_tour=True,parents=True) self.bfsd_idx=[None]*self.V for i,x in enumerate(self.bfsd_tour): self.bfsd_idx[x]=i for i in range(self.V-1,-1,-1): x=self.bfsd_tour[i] self.bfsd_L[x][0]=i self.bfsd_R[x][0]=i+1 for y in self.graph[x]: if y==self.bfsd_parents[x]: continue for d in range(1,self.bfsd_D+1): self.bfsd_L[x][d]=min(self.bfsd_L[x][d],self.bfsd_L[y][d-1]) self.bfsd_R[x][d]=max(self.bfsd_R[x][d],self.bfsd_R[y][d-1]) def BFSD(self,x,d,annular=False): assert d<=self.bfsd_D bfsd=[] def push_LR(l,r): if l1: i>>= 1 self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Build(self,lst): for i,x in enumerate(lst,self.le): self.segment_tree[i]=x for i in range(self.le-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Fold(self,L=None,R=None): if L==None: L=self.le else: assert 0<=L<=self.N L+=self.le if R==None: R=self.le*2 else: assert 0<=R<=self.N R+=self.le vL=self.e vR=self.e while L>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None: L=self.le else: assert 0<=L<=self.N L+=self.le if R==None: R=self.le*2 else: assert 0<=R<=self.N R+=self.le if L==R: return None x=self.Fold(L-self.le,R-self.le) while L>=1 R>>=1 while i>=1 r>>=1 if f(self.f(vl,vr)): return self.N v=self.e while True: while L%2==0: L>>=1 vv=self.f(v,self.segment_tree[L]) if f(vv): v=vv L+=1 else: while L>=1 r>>=1 if f(self.f(vl,vr)): return 0 v=self.e while True: R-=1 while R>1 and R%2: R>>=1 vv=self.f(self.segment_tree[R],v) if f(vv): v=vv else: while R