結果

問題 No.697 池の数はいくつか
ユーザー KazunKazun
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
62,132 KB
testcase_01 MLE -
testcase_02 AC 46 ms
63,248 KB
testcase_03 MLE -
testcase_04 AC 44 ms
56,556 KB
testcase_05 AC 44 ms
55,620 KB
testcase_06 AC 45 ms
56,200 KB
testcase_07 AC 44 ms
55,112 KB
testcase_08 AC 40 ms
53,676 KB
testcase_09 AC 44 ms
55,408 KB
testcase_10 AC 45 ms
56,744 KB
testcase_11 AC 42 ms
55,356 KB
testcase_12 AC 38 ms
53,440 KB
testcase_13 AC 45 ms
55,836 KB
testcase_14 AC 44 ms
55,380 KB
testcase_15 AC 43 ms
55,564 KB
testcase_16 AC 44 ms
56,140 KB
testcase_17 AC 43 ms
55,208 KB
testcase_18 AC 44 ms
55,948 KB
testcase_19 AC 44 ms
55,644 KB
testcase_20 AC 44 ms
55,596 KB
testcase_21 AC 45 ms
56,596 KB
testcase_22 AC 43 ms
55,840 KB
testcase_23 AC 43 ms
55,368 KB
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 MLE -
testcase_30 MLE -
testcase_31 MLE -
testcase_32 MLE -
testcase_33 MLE -
testcase_34 MLE -
権限があれば一括ダウンロードができます

ソースコード

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))
0