結果

問題 No.697 池の数はいくつか
ユーザー 👑 Kazun
提出日時 2020-07-18 01:15:13
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,838 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 906,800 KB
最終ジャッジ日時 2024-11-25 16:20:40
合計ジャッジ時間 58,042 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 20 TLE * 5 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

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 Connected_Component_Number(G):
T={v:False for v in G.adjacent}
C=0
for v in G.adjacent:
if not T[v]:
X=G.connected_component(v)
for x in X:
T[x]=True
C+=1
return C
#
def Grid_Graph(m,n):
E=[]
for x in range(1,m+1):
E+=[(x,y) for y in range(1,n+1)]
G=Graph(E)
H=[(1,0),(0,1)]
for y in range(1,n+1):
for x in range(1,m+1):
for a,b in H:
p=x+a
q=y+b
if 1<=p<=m and 1<=q<=n:
G.add_edge((x,y),(p,q))
return G
#-----------------------------------------------------------
H,W=map(int,input().split())
G=Grid_Graph(H,W)
for i in range(1,H+1):
A=list(map(int,input().split()))
for j in range(1,W+1):
if A[j-1]==0:
G.remove_vertex((i,j))
print(Connected_Component_Number(G))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0