結果
| 問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2022-03-29 23:39:17 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,236 ms / 4,000 ms |
| コード長 | 7,488 bytes |
| 記録 | |
| コンパイル時間 | 297 ms |
| コンパイル使用メモリ | 82,944 KB |
| 実行使用メモリ | 249,952 KB |
| 最終ジャッジ日時 | 2024-10-09 06:35:31 |
| 合計ジャッジ時間 | 27,813 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 41 |
ソースコード
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<w:
yield (v,w)
def Lowlink(G, mode=0):
""" G の ord, lowlink を求める.
G: Graph
output: (ord, lowlink)
"""
from collections import deque
N=G.vertex_count()
ord=[-1]*N; low=[-1]*N
flag=[0]*N
adj=G.adjacent
parent=[-1]*N
#BFSパート
for v in range(N):
if flag[v]:
continue
k=0
S=deque([v])
T=[]
while S:
u=S.pop()
if flag[u]:
continue
T.append(u)
ord[u]=k
k+=1
flag[u]=1
for w in adj[u]:
if not flag[w]:
S.append(w)
parent[w]=u
for 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, low
else:
return ord, low, parent
#橋列挙
def Bridge(G):
""" G にある橋を列挙する.
G: Graph
"""
ord,low=Lowlink(G)
return [(u,v) for u,v in G.edge_yielder() if ord[u]<low[v] or ord[v]<low[u]]
def Connected_Component_Decomposition(G, mode=0):
""" 連結成分毎に分解する.
G: Graph
mode: 0→連結成分, 1, 連結成分番号, 2→ (連結成分, 連結成分番号)"""
from collections import deque
N=G.vertex_count()
T=[-1]*N
C=[]
k=0
for v in range(N):
if T[v]==-1:
Q=deque([v]); T[v]=k
c=[]
while Q:
u=Q.popleft()
c.append(u)
for w in G.adjacent[u]:
if T[w]==-1:
T[w]=k
Q.append(w)
k+=1
C.append(c)
if mode==0:
return C
elif mode==1:
return T
else:
return C,T
#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
N,M,Q=map(int,input().split())
G=Graph(N+1)
for _ in range(M):
u,v=map(int,input().split())
G.add_edge(u,v)
H=Graph(N+1)
for u,v in Bridge(G):
H.add_edge(u,v)
Id=Connected_Component_Decomposition(H,1)
Ans=[""]*Q
for q in range(Q):
x,y=map(int,input().split())
Ans[q]="Yes" if Id[x]==Id[y] else "No"
write("\n".join(Ans))