結果

問題 No.1254 補強への架け橋
ユーザー 👑 Kazun
提出日時 2020-08-09 03:58:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,681 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 853,160 KB
最終ジャッジ日時 2024-10-13 18:13:24
合計ジャッジ時間 32,202 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 3
other WA * 121 MLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Graph:
#
def __init__(self,vertex=[]):
self.vertex=list(vertex)
self.edge_number=0
self.adjacent={v:set() for v in vertex}
#
def add_vertex(self,*adder):
k=len(self.vertex)
m=0
for u in adder:
if u not in self.adjacent:
self.adjacent[u]=set()
self.vertex.append(u)
#
def add_edge(self,From,To):
for w in [From,To]:
if w not in self.adjacent:
self.add_vertex(w)
if To not in self.adjacent[From]:
self.adjacent[From].add(To)
self.adjacent[To].add(From)
self.edge_number+=1
#
def remove_edge(self,u,v):
for w in [u,v]:
if w not in self.adjacent:
self.add_vertex(w)
if u in self.adjacent[v]:
self.adjacent[u].remove(v)
self.adjacent[v].remove(u)
self.edge_number-=1
#
def remove_vertex(self,*v):
for w in v:
if w in self.adjacent:
self.edge_number-=len(self.adjacent[w])
for u in self.adjacent[w]:
self.adjacent[u].remove(w)
del self.adjacent[w]
#Walk
def add_walk(self,*walk):
n=len(walk)
for i in range(n-1):
self.add_edge(walk[i],walk[i+1])
#Cycle
def add_cycle(self,*cycle):
self.add_walk(*cycle)
self.add_edge(cycle[-1],cycle[0])
#
def __vertex_swap(self,p,q):
self.vertex.sort()
#
def vertex_exist(self,v):
return v in self.adjacent
#
def edge_exist(self,u,v):
if not(self.vertex_exist(u) and self.vertex_exist(v)):
return False
return u in self.adjacent[v]
#
def neighbohood(self,v):
if not self.vertex_exist(v):
return []
return list(self.adjacent[v])
#
def degree(self,v):
if not self.vertex_exist(v):
return 0
return len(self.adjacent[v])
#
def vertex_count(self):
return len(self.vertex)
#
def edge_count(self):
return self.edge_number
#v
def connected_component(self,v):
if v not in self.adjacent:
return []
from collections import deque
T={u:False for u in self.adjacent}
T[v]=True
S=deque([v])
while S:
u=S.popleft()
for w in self.adjacent[u]:
if not T[w]:
T[w]=True
S.append(w)
return [x for x in self.adjacent if T[x]]
#
def distance(self,u,v):
from collections import deque
inf=float("inf")
T={v:inf for v in G.vertex}
if u==v:
return 0
Q=deque([u])
T[u]=0
while Q:
w=Q.popleft()
for x in G.adjacent[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
if x==v:
return T[x]
return inf
#
def shortest_path(self,u,v):
from collections import deque
inf=float("inf")
T={v:[] for v in G.vertex}
if u==v:
return 0
Q=deque([u])
T[u]=[u]
while Q:
w=Q.popleft()
for x in G.adjacent[w]:
if not T[x]:
T[x]=T[w]+[x]
Q.append(x)
if x==v:
return T[x]
return None
def DFS_Tree(G):
from collections import deque
T={v:False for v in G.vertex}
v=G.vertex[0]
D={v:float("inf") for v in G.vertex}
S=deque([v])
T[v]=True
while S:
v=S.pop()
for u in G.adjacent[v]:
if not T[u]:
T[u]=True
S.append(u)
B.remove((min(u,v),max(u,v)))
#-------------------------------------------------
from collections import deque
N=int(input())
G=Graph(list(range(1,N+1)))
B=set()
for _ in range(N):
u,v=map(int,input().split())
G.add_edge(u,v)
x,y=min(u,v),max(u,v)
B.add((x,y))
DFS_Tree(G)
u,v=B.pop()
G.remove_edge(u,v)
P=G.shortest_path(u,v)+[u]
L=len(P)-1
X=[0]*L
for i in range(L):
a,b=min(P[i],P[i+1]),max(P[i],P[i+1])
X[i]=(a,b)
X.sort()
print(L)
print("\n".join(map(lambda x:"{} {}".format(x[0],x[1]),X)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0