Problem p02561 (python)

Fixed submission:
class Weigthed_Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Flow_by_Dinic(D,source,sink,Mode=False):
    from collections import deque
    from copy import copy

    """Source sからSink tへの最大流問題をDinic法で解く.\n

    Mode:
    True---各頂点の流し方も返す
    False---解答のみ
    (参考元:https://tjkendev.github.io/procon-library/python/max_flow/dinic.html)
    """
    def bfs(s,t):
        for v in D.vertex:
            Level[v]=None

        Q=deque([s])
        Level[s]=0

        while Q:
            v=Q.popleft()
            for w,cap,_ in H[v]:
                if cap and Level[w] is None:
                    Level[w]=Level[v]+1
                    Q.append(w)

        return Level[t] is not None

    def dfs(v,t,f):
        if v==t:
            return f

        for e in H[v]:
            w,cap,rev=e
            if cap and Level[v]<Level[w]:
                d=dfs(w,t,min(f,cap))

                if d:
                    e[1]-=d
                    rev[1]+=d
                    return d
        return 0

    s,t=source,sink
    inf=float("inf")
    flow=0
    Level={v:None for v in D.vertex}

    H={v:[] for v in D.vertex}

    for u in D.vertex:
        for v in D.adjacent_out[u]:
            F=[v,D.adjacent_out[u][v],None]
            F[2]=B=[u,0,F]
            H[u].append(F)
            H[v].append(B)

    while bfs(s,t):
        f=inf
        while f:
            f=dfs(s,t,inf)
            flow+=f

    if Mode:
        R={}
        for v in D.vertex:
            R[v]={}
            for S in H[v]:
                w=S[0]
                if w in D.adjacent_out[v]:
                    R[v][w]=S[-1][1]

        return flow,R
    else:
        return flow
#================================================
N,M=map(int,input().split())
D=Weigthed_Digraph([(y,x) for x in range(1,M+1) for y in range(1,N+1)])
D.add_vertex("s","t")

S=["*"*(M+2) for _ in range(N+2)]
for i in range(1,N+1):
    S[i]="*"+input()+"*"

H=[(1,0),(-1,0),(0,1),(0,-1)]
for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]!=".":
            continue

        if (x+y)%2:
            D.add_edge("s",(y,x),1)
            for (a,b) in H:
                if S[y+a][x+b]==".":
                    D.add_edge((y,x),(y+a,x+b),1)
        else:
            D.add_edge((y,x),"t",1)

flow,F=Flow_by_Dinic(D,"s","t",True)

U=[[S[j][i] for i in range(M+2)] for j in range(N+2)]
for y in range(1,N+1):
    for x in range(1,M+1):
        for C in F[(y,x)]:
            if isinstance(C,str):
                continue
            elif F[(y,x)][C]==0:
                continue

            q,p=C
            if (y+1==q) and (x==p):
                alpha,beta="v","^"
            elif (y-1==q) and (x==p):
                alpha,beta="^","v"
            elif (y==q) and (x+1==p):
                alpha,beta=">","<"
            elif (y==q) and (x-1==p):
                alpha,beta="<",">"

            U[y][x]=alpha
            U[q][p]=beta

print(flow)
Y=["".join(T[1:-1]) for T in U[1:-1]]
print("\n".join(Y))

Buggy submission (verdict: Runtime Error):
class Weigthed_Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Flow(D,source,sink,Mode=False):
    """Source sからSink tへの最大流問題を解く.
    Mode:
    True---各頂点の流し方も返す
    False---解答のみ
    """
    import sys
    sys.setrecursionlimit(10**6)

    s,t=source,sink

    H={v:[] for v in D.vertex}

    for u in D.vertex:
        for v in D.adjacent_out[u]:
            F=[v,D.adjacent_out[u][v],None]
            F[2]=B=[u,0,F]
            H[u].append(F)
            H[v].append(B)

    def dfs(v,t,f):
        if v==t:
            return f

        U[v]=True
        for e in H[v]:
            w,cap,inv=e

            if cap and (not U[w]):
                d=dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    inv[1]+=d
                    return d
        return 0

    inf=float("inf")
    f=inf
    flow=0
    while f:
        U={v:False for v in D.vertex}
        f=dfs(s,t,inf)
        flow+=f

    if Mode:
        R={}
        for v in D.vertex:
            R[v]={}
            for S in H[v]:
                w=S[0]
                if w in D.adjacent_out[v]:
                    R[v][w]=S[-1][1]

        return flow,R
    else:
        return flow
#================================================
N,M=map(int,input().split())

V=[(i,j) for i in range(1,N+1) for j in range(1,M+1)]
D=Weigthed_Digraph(V)

S=[""]*(N+2)
S[0]=S[-1]="*"*(M+2)

for i in range(1,N+1):
    S[i]="*"+input()+"*"

H=[(0,1),(0,-1),(1,0),(-1,0)]
for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]!="." or (x+y)%2==0:
            continue

        for (a,b) in H:
            if S[y+a][x+b]==".":
                D.add_edge((y,x),(y+a,x+b),1)

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]==".":
            if (x+y)%2:
                D.add_edge("s",(y,x),1)
            else:
                D.add_edge((y,x),"t",1)

flow,F=Flow(D,"s","t",True)

U=[[S[j][i] for i in range(M+2)] for j in range(N+2)]

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]=="#":
            continue

        for C in F[(y,x)]:
            try:
                q,p=C
                if F[(y,x)][(q,p)]:
                    if (y+1,x)==(q,p):
                        U[y][x]  ="v"
                        U[y+1][x]="^"
                    elif (y-1,x)==(q,p):
                        U[y][x]  ="^"
                        U[y-1][x]="v"
                    elif (y,x+1)==(q,p):
                        U[y][x]  =">"
                        U[y][x+1]="<"
                    elif (y,x-1)==(q,p):
                        U[y][x]  ="<"
                        U[y][x-1]=">"
            except:
                pass

print(flow)
Y=["".join(U[k][1:-1]) for k in range(1,N+1)]
print("\n".join(Y))

Buggy submission (verdict: Runtime Error):
class Weigthed_Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Flow(D,source,sink,Mode=False):
    """Source sからSink tへの最大流問題を解く.

    Mode:
    True---各頂点の流し方も返す
    False---解答のみ
    """
    s,t=source,sink

    H={v:[] for v in D.vertex}

    for u in D.vertex:
        for v in D.adjacent_out[u]:
            F=[v,D.adjacent_out[u][v],None]
            F[2]=B=[u,0,F]
            H[u].append(F)
            H[v].append(B)

    def dfs(v,t,f):
        if v==t:
            return f

        U[v]=True
        for e in H[v]:
            w,cap,inv=e

            if cap and (not U[w]):
                d=dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    inv[1]+=d
                    return d
        return 0

    inf=float("inf")
    f=inf
    flow=0
    while f:
        U={v:False for v in D.vertex}
        f=dfs(s,t,inf)
        flow+=f

    if Mode:
        R={}
        for v in D.vertex:
            R[v]={}
            for S in H[v]:
                w=S[0]
                if w in D.adjacent_out[v]:
                    R[v][w]=S[-1][1]

        return flow,R
    else:
        return flow
#================================================
from sys import setrecursionlimit
setrecursionlimit(10**5)

N,M=map(int,input().split())

V=[(i,j) for i in range(1,N+1) for j in range(1,M+1)]
D=Weigthed_Digraph(V)

S=[""]*(N+2)
S[0]=S[-1]="*"*(M+2)

for i in range(1,N+1):
    S[i]="*"+input()+"*"

H=[(0,1),(0,-1),(1,0),(-1,0)]
for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]!="." or (x+y)%2==0:
            continue

        for (a,b) in H:
            if S[y+a][x+b]==".":
                D.add_edge((y,x),(y+a,x+b),1)

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]==".":
            if (x+y)%2:
                D.add_edge("s",(y,x),1)
            else:
                D.add_edge((y,x),"t",1)

flow,F=Flow(D,"s","t",True)

U=[[S[j][i] for i in range(M+2)] for j in range(N+2)]

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]=="#":
            continue

        for C in F[(y,x)]:
            try:
                q,p=C
                if F[(y,x)][(q,p)]:
                    if (y+1,x)==(q,p):
                        U[y][x]  ="v"
                        U[y+1][x]="^"
                    elif (y-1,x)==(q,p):
                        U[y][x]  ="^"
                        U[y-1][x]="v"
                    elif (y,x+1)==(q,p):
                        U[y][x]  =">"
                        U[y][x+1]="<"
                    elif (y,x-1)==(q,p):
                        U[y][x]  ="<"
                        U[y][x-1]=">"
            except:
                pass

print(flow)
Y=["".join(U[k][1:-1]) for k in range(1,N+1)]
print("\n".join(Y))

Buggy submission (verdict: Runtime Error):
class Weigthed_Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Flow(D,source,sink,Mode=False):
    """Source sからSink tへの最大流問題を解く.

    Mode:
    True---各頂点の流し方も返す
    False---解答のみ
    """
    s,t=source,sink

    H={v:[] for v in D.vertex}

    for u in D.vertex:
        for v in D.adjacent_out[u]:
            F=[v,D.adjacent_out[u][v],None]
            F[2]=B=[u,0,F]
            H[u].append(F)
            H[v].append(B)

    def dfs(v,t,f):
        if v==t:
            return f

        U[v]=True
        for e in H[v]:
            w,cap,inv=e

            if cap and (not U[w]):
                d=dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    inv[1]+=d
                    return d
        return 0

    inf=float("inf")
    f=inf
    flow=0
    while f:
        U={v:False for v in D.vertex}
        f=dfs(s,t,inf)
        flow+=f

    if Mode:
        R={}
        for v in D.vertex:
            R[v]={}
            for S in H[v]:
                w=S[0]
                if w in D.adjacent_out[v]:
                    R[v][w]=S[-1][1]

        return flow,R
    else:
        return flow
#================================================
N,M=map(int,input().split())
V=[(i,j) for i in range(1,N+1) for j in range(1,M+1)]
D=Weigthed_Digraph(V)

S=[""]*(N+2)
S[0]=S[-1]="*"*(M+2)

for i in range(1,N+1):
    S[i]="*"+input()+"*"

H=[(0,1),(0,-1),(1,0),(-1,0)]
for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]!="." or (x+y)%2==0:
            continue

        for (a,b) in H:
            if S[y+a][x+b]==".":
                D.add_edge((y,x),(y+a,x+b),1)

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]==".":
            if (x+y)%2:
                D.add_edge("s",(y,x),1)
            else:
                D.add_edge((y,x),"t",1)

flow,F=Flow(D,"s","t",True)

U=[[S[j][i] for i in range(M+2)] for j in range(N+2)]

for y in range(1,N+1):
    for x in range(1,M+1):
        if S[y][x]=="#":
            continue

        for C in F[(y,x)]:
            try:
                q,p=C
                if F[(y,x)][(q,p)]:
                    if (y+1,x)==(q,p):
                        U[y][x]  ="v"
                        U[y+1][x]="^"
                        flag=False
                    elif (y-1,x)==(q,p):
                        U[y][x]  ="^"
                        U[y-1][x]="v"
                        flag=False
                    elif (y,x+1)==(q,p):
                        U[y][x]  =">"
                        U[y][x+1]="<"
                        flag=False
                    elif (y,x-1)==(q,p):
                        U[y][x]  ="<"
                        U[y][x-1]=">"
                        flag=False
            except:
                pass

print(flow)
Y=["".join(U[k][1:-1]) for k in range(1,N+1)]
print("\n".join(Y))