結果
| 問題 |
No.812 Change of Class
|
| コンテスト | |
| ユーザー |
 None
|
| 提出日時 | 2021-03-18 06:45:21 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,374 ms / 4,000 ms |
| コード長 | 22,171 bytes |
| コンパイル時間 | 269 ms |
| コンパイル使用メモリ | 82,536 KB |
| 実行使用メモリ | 176,076 KB |
| 最終ジャッジ日時 | 2024-11-16 00:26:25 |
| 合計ジャッジ時間 | 32,320 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 60 |
ソースコード
class Graph:
def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
self.n = n
self.directed = directed
self.decrement = decrement
self.destroy = destroy
self.edges = [set() for _ in range(self.n)]
self.parent = [-1]*self.n
for x, y in edges:
self.add_edge(x,y)
def add_edge(self, x, y):
if self.decrement:
x -= 1
y -= 1
self.edges[x].add(y)
if self.directed == False:
self.edges[y].add(x)
def add_adjacent_list(self, i, adjacent_list):
if self.decrement:
self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
else:
self.edges[i] = set(adjacent_list)
def bfs(self, start=None, goal=-1, time=0, save=False):
"""
:param start: スタート地点
:param goal: ゴール地点
:param save: True = 前回の探索結果を保持する
:return: (ループがあっても)最短距離。存在しなければ -1
"""
if start is None: start=self.decrement
start,goal=start-self.decrement,goal-self.decrement
if not save:
self.parent = [-1] * self.n
p, t = start, time
self.parent[p] = -2
next_set = deque([(p, t)])
if p==goal:
return t
while next_set:
p, t = next_set.popleft()
for q in self.edges[p]:
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
continue
if self.parent[q] != -1:
""" サイクル時の処理 """
continue
if q == goal:
self.parent[q]=p
return t + 1
self.parent[q] = p
next_set.append((q, t + 1))
return -1
def connection_counter(self):
"""
:return: 連結成分の個数。有効グラフではあまり意味がない。
"""
cnt = 0
self.parent = [-1] * self.n
for start in range(self.n):
if self.parent[start] == -1:
cnt += 1
self.bfs(start + self.decrement, save=True)
return cnt
def connection_detail(self):
"""
:return: 連結成分の(頂点数, 辺の数)。有効グラフではあまり意味がない。
備考: 木であるための必要十分条件は M=N-1
"""
ver_edge=[]
self.parent = [-1] * self.n
for start in range(self.n):
if self.parent[start] == -1:
ver_cnt, edge_cnt = self._detail(start + self.decrement)
ver_edge.append((ver_cnt, edge_cnt))
return ver_edge
def _detail(self, start=None):
"""
:param start: スタート地点
:param save: True = 前回の探索結果を保持する
"""
if start is None: start=self.decrement
start=start-self.decrement
p, t = start, 0
self.parent[p] = -2
next_set = deque([(p, t)])
sub_edges,sub_vers = set(),set()
while next_set:
p, t = next_set.popleft()
sub_vers.add(p)
for q in self.edges[p]:
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
continue
sub_edges.add((min(p,q),max(p,q)))
if self.parent[q] != -1:
""" サイクル時の処理 """
continue
self.parent[q] = p
next_set.append((q, t + 1))
return len(sub_vers),len(sub_edges)
def distance_list(self, start=None, save=False):
"""
:param start: スタート地点
:return: スタート地点から各点への距離のリスト
※ 距離無限大が -1 になっている点に注意！！！
"""
dist = [-1]*self.n
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
p, t = start, 0
self.parent[p] = -2
dist[p] = 0
next_set = deque([(p, t)])
while next_set:
p, t = next_set.popleft()
for q in self.edges[p]:
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
continue
if self.parent[q] != -1:
""" サイクル時の処理 """
continue
dist[q] = t + 1
self.parent[q] = p
next_set.append((q, t + 1))
return dist
def parent_list(self, start=None):
"""
:return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号
訪問しない場合は -1 を返す
"""
if start is None: start=self.decrement
self.distance_list(start)
return list(p + self.decrement for p in self.parent[1:])
def most_distant_point(self, start=None, save=False):
"""
計算量 O(N)
:return: (start から最も遠い頂点, 距離)
"""
if not save:
self.parent = [-1] * self.n
if start is None: start=self.decrement
start=start-self.decrement
res = (start, 0)
temp = 0
for i, dist in enumerate(self.distance_list(start+self.decrement, save=save)):
if dist > temp:
temp = dist
res = (i + self.decrement, dist)
return res
def diameter(self, save=False):
"""
計算量 O(N)
:return: 木の直径(最も離れた二頂点間の距離)を返す
"""
if not save:
self.parent = [-1] * self.n
p = self.most_distant_point(save=save)
res = self.most_distant_point(start=p[0], save=save)
return res[1]
def all_cycle(self):
"""
無向グラフ用 O(V(V+E))
"""
res=[]
for start in range(self.n):
flg=0
self.parent = [-1] * self.n
p, t = start, 0
self.parent[p] = -2
next_set=deque()
starts=set()
for q in self.edges[p]:
next_set.append((q, t))
self.parent[q]=p
starts.add(q)
while next_set and flg==0:
p, t = next_set.popleft()
for q in self.edges[p]:
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
continue
if self.parent[q] != -1:
""" サイクル時の処理 """
if q in starts:
cycle=[q+self.decrement]
r=p
while r not in starts:
cycle.append(r+self.decrement)
r=self.parent[r]
if r<0: return -1
cycle.append(r+self.decrement)
cycle.append(start+self.decrement)
res.append(cycle[::-1])
flg=1
break
continue
self.parent[q] = p
next_set.append((q, t + 1))
return res
def minimum_cycle_directed(self):
"""
有向グラフ用 O(V(V+E))
"""
INF=10**18
dist=[]
history=[]
for i in range(self.n):
dist.append(self.distance_list(start=i+self.decrement,save=False,INF=INF)[:])
history.append(self.parent[:])
res=INF
s,g=None,None
for i in range(self.n):
for j in self.edges[i]:
if dist[j][i]+1<res:
res=dist[j][i]+1
s,g=i,j
if res>=INF:
return []
else:
self.parent=history[g]
return self.path_restoring(g+self.decrement,s+self.decrement)
def dfs(self, start=None, goal=-1, time=0, save=False):
"""
:param start: スタート地点
:param goal: ゴール地点
:param save: True = 前回の探索結果を保持する
:return: ゴール地点までの距離。存在しなければ -1。ループがある時は最短距離とは限らないため注意。
"""
if start is None: start=self.decrement
start,goal=start-self.decrement,goal-self.decrement
if not save:
self.parent = [-1] * self.n
if self.destroy:
edges2 = self.edges
else:
edges2 = [self.edges[p].copy() for p in range(self.n)]
parent,directed=self.parent,self.directed
p, t = start, time
parent[p] = -2
if p==goal:
return t
while True:
if edges2[p]:
q = edges2[p].pop()
if q == parent[p] and not directed:
""" 逆流した時の処理 """
continue
if parent[q] != -1:
""" サイクルで同一点を訪れた時の処理 """
continue
if q == goal:
""" ゴール時の処理"""
parent[q]=p
return t + 1
""" p から q への引継ぎ"""
parent[q] = p
p, t = q, t + 1
else:
""" p から進める点がもう無い時の点 p における処理 """
if p == start and t == time:
break
p, t = parent[p], t-1
""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
return -1
def cycle_detector(self, start=None, time=0, save=False):
"""
:param p: スタート地点
:param save: True = 前回の探索結果を保持する(遅い)
:return: サイクルリストを返す。存在しない場合は []
"""
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
self.finished=[0]*self.n
if self.destroy:
edges2 = self.edges
else:
edges2 = [self.edges[p].copy() for p in range(self.n)]
p, t = start, time
self.parent[p] = -2
history = [p+self.decrement]
cycle = []
while True:
if edges2[p]:
q = edges2[p].pop()
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
""""""""""""""""""""
continue
if self.parent[q] != -1:
""" サイクルで同一点を訪れた時の処理 """
if not self.finished[q] and not cycle:
cycle_start=history.index(q+self.decrement)
if save==False:
return history[cycle_start:]
else:
cycle = history[cycle_start:]
""""""""""""""""""""
continue
""" p から q への引継ぎ"""
""""""""""""""""""""
history.append(q+self.decrement)
self.parent[q] = p
p, t = q, t + 1
else:
""" p から進める点がもう無い時の点 p における処理 """
self.finished[p]=1
history.pop()
""""""""""""""""""""
if p == start and t == time:
break
p, t = self.parent[p], t-1
""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
""""""""""""""""""""
return cycle
def tree_counter(self, detail=False):
"""
:param detail: True = サイクルのリストを返す
:return: 木(閉路を含まない)の個数を返す
"""
self.destroy=True # これをしないと計算量が壊れる
self.parent = [-1] * self.n
self.finished=[0]*self.n
connection_number = 0
cycle_list = []
for p in range(self.n):
if self.parent[p] == -1:
connection_number += 1
cycle = self.cycle_detector(p + self.decrement, save=True)
if cycle:
cycle_list.append(cycle)
if not detail:
return connection_number - len(cycle_list)
else:
return cycle_list
def path_detector(self, start=None, time=0, save=False):
"""
:param p: スタート地点
:param save: True = 前回の探索結果を保持する
:return: 各点までの距離と何番目に発見したかを返す
"""
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
edges2= []
for i in range(self.n):
edges2.append(sorted(self.edges[i], reverse=True))
p, t = start, time
self.parent[p] = -2
full_path = [(p + self.decrement,t)]
while True:
if edges2[p]:
q = edges2[p].pop()
if q == self.parent[p] and not self.directed:
""" 逆流した時の処理 """
""""""""""""""""""""
continue
if self.parent[q] != -1:
""" サイクルで同一点を訪れた時の処理 """
""""""""""""""""""""
continue
""" p から q への引継ぎ"""
""""""""""""""""""""
self.parent[q] = p
p, t = q, t + 1
full_path.append((p + self.decrement, t))
else:
""" p から進める点がもう無い時の点 p における処理 """
""""""""""""""""""""
if p == start and t == time:
break
p, t = self.parent[p], t-1
""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
full_path.append((p + self.decrement, t))
""""""""""""""""""""
return full_path
def path_restoring(self,start,goal):
start,goal=start-self.decrement,goal-self.decrement
q=goal
res=[]
while q!=start:
res.append(q+self.decrement)
q=self.parent[q]
if q<0: return -1
res.append(start+self.decrement)
return res[::-1]
def draw(self):
"""
:return: グラフを可視化
"""
import matplotlib.pyplot as plt
import networkx as nx
if self.directed:
G = nx.DiGraph()
else:
G = nx.Graph()
for x in range(self.n):
for y in self.edges[x]:
G.add_edge(x + self.decrement, y + self.decrement)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos, connectionstyle='arc3, rad = 0.1')
plt.axis("off")
plt.show()
##################################################################################################
def make_graph(N_min=2, N_max=5, M_min=1, M_max=10, directed=False,decrement=True):
"""
自己ループの無いグラフを生成。N>=2
:param directed: True = 有効グラフ
:param decrement: True = 1-indexed
:return:
"""
import random
input_data = []
global input
N=random.randint(N_min,N_max,)
if N>2:
M_max2=(3*N-6)*(1+directed)
else:
M_max2=1
M=random.randint(max(1,M_min),min(M_max,M_max2))
print("#########")
edges=set()
for _ in range(1,M+1):
edge=random.sample(range(decrement,N+decrement),2)
if directed==False:
edge.sort()
edge=tuple(edge)
if edge not in edges:
edges.add(edge)
print(N,len(edges))
input_data.append(" ".join(map(str,(N,len(edges)))))
for edge in edges:
print(*edge)
input_data.append(" ".join(map(str,edge)))
print("#########")
input_data=iter(input_data)
input = lambda: next(input_data)
def draw(N,edges,decrement=1):
import matplotlib.pyplot as plt
import networkx as nx
G=nx.Graph()
for x in range(N):
for y in edges[x]:
G.add_edge(x+decrement,y+decrement)
pos=nx.spring_layout(G)
nx.draw_networkx(G,pos)
plt.axis("off")
plt.show()
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
""" 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)"""
tmp = []
parents = self.parents
while parents[x] >= 0:
tmp.append(x)
x = parents[x]
for y in tmp:
parents[y] = x
return x
def union(self, x, y):
""" 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。"""
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def same(self, x, y):
""" xとyが同じ根の子かを判定 """
return self.find(x) == self.find(y)
def size(self, x):
""" xの根のparent(= 要素数)を返す """
return -self.parents[self.find(x)]
def members(self, x):
""" xが属するグループの要素をリストとして返す O(N)"""
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
""" 全ての根の要素をリストとして返す O(N)"""
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
""" グループの数を返す O(N)"""
return len(self.roots())
def size_list(self):
""" 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""
return [-x for x in self.parents if x < 0]
def all_group_members(self):
""" {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)"""
res = [[] for _ in range(self.n)]
for i in range(self.n):
x = self.find(i)
res[x].append(i)
return {r: res[r] for r in self.roots()}
def __str__(self):
return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
######################################################################
def example_tree(N=10,show=True,decrement=1):
global input
# decrement=True: create 1-indexed tree
def find(x):
tmp=[]
while parents[x]>=0:
tmp.append(x)
x=parents[x]
for y in tmp: parents[y]=x
return x
def union(x,y):
x,y=find(x),find(y)
if x==y: return
if parents[x]>parents[y]: x,y=y,x
parents[x]+=parents[y]
parents[y]=x
def same(x,y):
return find(x)==find(y)
import random
# N = random.randint(2, N)
parents=[-1]*N
edges=[]
input_data=[]
input_data.append(str(N))
for i in range(N-1):
while True:
j=random.randint(0,N-1)
if same(i,j): continue
union(i,j)
edges.append((i+decrement,j+decrement))
break
for i,j in edges:
input_data.append(" ".join(map(str,(i,j))))
input_data=iter(input_data)
input=lambda:next(input_data)
if show:
print("#######################")
print(N)
for p in edges:
print(*p)
print("#######################")
return edges
def example_special_tree(N, type, show=True, decrement=1):
global input
edges = []
if type=="path":
for i in range(N-1):
edges.append((i+decrement,i+1+decrement))
if type=="star":
for i in range(N-1):
edges.append((i,i+1+decrement))
if type=="binary":
i = 1
while True:
if (i<<1) >= N: break
edges.append((i-1+decrement, (i<<1)-1+decrement))
if (i<<1)+1 >= N: break
edges.append((i-1+decrement, (i<<1)+decrement))
i += 1
input_data=[]
input_data.append(str(N))
for i,j in edges:
input_data.append(" ".join(map(str,(i,j))))
input_data=iter(input_data)
input=lambda:next(input_data)
if show:
print("#######################")
print(N)
for p in edges:
print(*p)
print("#######################")
return edges
def example():
global input
example=iter(
"""
6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2
"""
.strip().split("\n"))
input=lambda:next(example)
######################################################################
import sys
input=sys.stdin.readline
from collections import deque
# example()
# make_graph(N_min=7,N_max=7,M_min=10,M_max=10,directed=True)
N, M = map(int, input().split())
G = Graph(N, directed=False, decrement=True, destroy=False)
U = UnionFind(N)
for _ in range(M):
x, y = map(int, input().split())
G.add_edge(x, y)
U.union(x-1, y-1)
Q=int(input())
for _ in range(Q):
a=int(input())
p, dist = G.most_distant_point(start=a)
if dist==0:
print(0,0)
else:
k=(dist-1).bit_length()
print(U.size(a-1)-1, k)