結果
問題 | No.1254 補強への架け橋 |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
class Graph:#入力定義def __init__(self,vertex=[]):self.vertex=list(vertex)self.edge_number=0self.adjacent={v:set() for v in vertex}#頂点の追加def add_vertex(self,*adder):k=len(self.vertex)m=0for 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 Falsereturn 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 0return 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 dequeT={u:False for u in self.adjacent}T[v]=TrueS=deque([v])while S:u=S.popleft()for w in self.adjacent[u]:if not T[w]:T[w]=TrueS.append(w)return [x for x in self.adjacent if T[x]]#距離def distance(self,u,v):from collections import dequeinf=float("inf")T={v:inf for v in G.vertex}if u==v:return 0Q=deque([u])T[u]=0while Q:w=Q.popleft()for x in G.adjacent[w]:if T[x]==inf:T[x]=T[w]+1Q.append(x)if x==v:return T[x]return inf#最短路def shortest_path(self,u,v):from collections import dequeinf=float("inf")T={v:[] for v in G.vertex}if u==v:return 0Q=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 Nonedef DFS_Tree(G):from collections import dequeT={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]=Truewhile S:v=S.pop()for u in G.adjacent[v]:if not T[u]:T[u]=TrueS.append(u)B.remove((min(u,v),max(u,v)))#-------------------------------------------------from collections import dequeN=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)-1X=[0]*Lfor 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)))