Problem p02561 (python)

Fixed submission:
from collections import deque
class mf_graph:
    n=1
    g=[[] for i in range(1)]
    pos=[]
    def __init__(self,N):
        self.n=N
        self.g=[[] for i in range(N)]
    def add_edge(self,From,To,cap):
        assert 0<=From and From<self.n
        assert 0<=To and To<self.n
        assert 0<=cap
        m=len(self.pos)
        self.pos.append((From,len(self.g[From])))
        self.g[From].append({"to":To,"rev":len(self.g[To]),"cap":cap})
        self.g[To].append({"to":From,"rev":len(self.g[From])-1,"cap":0})
        return m
    def get_edge(self,i):
        m=len(self.pos)
        assert 0<=i and i<m
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        return {"from":self.pos[i][0],
                "to":_e["to"],
                "cap":_e["cap"]+_re["cap"],
                "flow":_re["cap"]}
    def edges(self):
        m=len(self.pos)
        result=[]
        for i in range(m):
            result.append(self.get_edge(i))
        return result
    def change_edge(self,i,new_cap,new_flow):
        m=len(self.pos)
        assert 0<=i and i<m
        assert 0<=new_flow and new_flow<=new_cap
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        _e["cap"]=new_cap-new_flow
        _re["cap"]=new_flow
    def flow(self,s,t,flow_limit=(2**31)-1):
        assert 0<=s and s<self.n
        assert 0<=t and t<self.n
        level=[0 for i in range(self.n)]
        Iter=[0 for i in range(self.n)]
        que=deque([])
        def bfs():
            for i in range(self.n):
                level[i]=-1
            level[s]=0
            que=deque([])
            que.append(s)
            while(len(que)>0):
                v=que.popleft()
                for e in self.g[v]:
                    if e["cap"]==0 or level[e["to"]]>=0:continue
                    level[e["to"]]=level[v]+1
                    if e["to"]==t:return
                    que.append(e["to"])
        def dfs(func,v,up):
            if (v==s):return up
            res=0
            level_v=level[v]
            for i in range(Iter[v],len(self.g[v])):
                e=self.g[v][i]
                if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue
                d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"]))
                if d<=0:continue
                self.g[v][i]["cap"]+=d
                self.g[e["to"]][e["rev"]]["cap"]-=d
                res+=d
                if res==up:break
            return res
        flow=0
        while(flow<flow_limit):
            bfs()
            if level[t]==-1:
                break
            for i in range(self.n):
                Iter[i]=0
            while(flow<flow_limit):
                f=dfs(dfs,t,flow_limit-flow)
                if not(f):break
                flow+=f
        return flow
    def min_cut(s):
        visited=[False for i in range(self.n)]
        que=deque([])
        que.append(s)
        while(len(que)>0):
            p=que.popleft()
            visited[p]=True
            for e in self.g[p]:
                if e["cap"] and not(visited[e["to"]]):
                    visited[e["to"]]=True
                    que.append(e["to"])
        return visited

N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
G=mf_graph(N*M+2)
for i in range(N):
    for j in range(M):
        if S[i][j]=="#":continue
        v=i*M+j
        if (i+j)%2==0:
            G.add_edge(N*M,v,1)
        else:
            G.add_edge(v,N*M+1,1)
for i in range(N):
    for j in range(M):
        if (i+j)%2 or S[i][j]=="#":continue
        v0=i*M+j
        if i>0 and S[i-1][j]==".":
            v1=(i-1)*M+j
            G.add_edge(v0,v1,1)
        if j>0 and S[i][j-1]==".":
            v1=i*M+(j-1)
            G.add_edge(v0,v1,1)
        if i+1<N and S[i+1][j]==".":
            v1=(i+1)*M+j
            G.add_edge(v0,v1,1)
        if j+1<M and S[i][j+1]==".":
            v1=i*M+(j+1)
            G.add_edge(v0,v1,1)

print(G.flow(N*M,N*M+1))

T=[[S[i][j] for j in range(M)] for i in range(N)]
for e in G.edges():
    if e["from"]==N*M or e["to"]==N*M+1 or e["flow"]==0:
        continue
    i0=e["from"]//M
    j0=e["from"]%M
    i1=e["to"]//M
    j1=e["to"]%M
    if i0==i1+1:
        T[i1][j1]="v"
        T[i0][j0]="^"
    elif j0==j1+1:
        T[i1][j1]=">";T[i0][j0]="<"
    elif i0==i1-1:
        T[i0][j0]="v"
        T[i1][j1]="^"
    else:
        T[i0][j0]=">";T[i1][j1]="<"

for i in range(N):
    print("".join(T[i]))

Buggy submission (verdict: Runtime Error):
from collections import deque
class mf_graph():
    n=1
    g=[[] for i in range(n)]
    pos=[]
    def __init__(self,N):
        self.n=N
        self.g=[[] for i in range(N)]
    def add_edge(self,f,t,cap):
        assert 0<=f<self.n, "0<=from<n,(from,n)=({0},{1})".format(f,self.n)
        assert 0<=t<self.n, "0<=to<n,(to,n)=({0},{1})".format(t,self.n)
        assert 0<=cap, "cap must be not negative,cap={0}".format(cap)
        m=len(self.pos)
        self.pos.append((f,len(self.g[f])))
        self.g[f].append({"to":t,"rev":len(self.g[t]),"cap":cap})
        self.g[t].append({"to":f,"rev":len(self.g[f])-1,"cap":0})
        return m
    def get_edge(self,i):
        m=len(self.pos)
        assert 0<=i<m, "0<=i<len(pos)=m,(i,m)=({0},{1})".format(i,m)
        e=self.g[self.pos[i][0]][self.pos[i][1]]
        re=self.g[e["to"]][e["rev"]]
        return {"from":self.pos[i][0],"to":e["to"],"cap":e["cap"]+re["cap"],"flow":re["cap"]}
    def edges(self):
        m=len(self.pos)
        result=[]
        for i in range(m):
            result.append(self.get_edge(i))
        return result
    def change_edge(self,i,new_cap,new_flow):
        m=len(self.pos)
        assert 0<=i<m,"0<=i<len(pos)=m,(i,m)=({0},{1})".format(i,m)
        assert 0<=new_flow and new_flow<=new_cap, "0<=new_flow<=new_cap,(new_flow,new_cap)=({0},{1})".format(new_flow,new_cap)
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[e["to"]][e["rev"]]
        _e["cap"]=new_cap-new_flow
        _re["cap"]=new_flow
    def flow(self,s,t,flow_limit):
        assert 0<=s<self.n, "0<=s<n,(s,n)=({0},{1})".format(s,self.n)
        assert 0<=t<self.n, "0<=t<n,(t,n)=({0},{1})".format(t,self.n)
        level=[0 for i in range(self.n)]
        iter0=[0 for i in range(self.n)]
        que=deque([])
        def bfs():
            level=[-1 for i in range(self.n)]
            que=deque([])
            que.append(s)
            while(len(que)>0):
                v=que.popleft()
                for e in self.g[v]:
                    if e["cap"]==0 or level[e["to"]]>=0:
                        continue
                    level[e["to"]]=level[v]+1
                    if e["to"]==t:
                        return
                    que.append(e["to"])
        def dfs(v,up):
            if v==s:
                return up
            res=0
            level_v=level[v]
            for i in range(iter0[v],len(self.g[v])):
                e=self.g[v][i]
                if level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0:
                    continue
                d=dfs(e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"]))
                if d<=0:
                    continue
                self.g[v][i]["cap"]=+d
                self.g[e["to"]][e["rev"]]-=d
                res+=d
                if res==up:
                    break
            return res
        flow=0
        while(flow<flow_limit):
            bfs()
            if level[t]==-1:
                break
            iter0=[0 for i in range(self.n)]
            while(flow<flow_limit):
                f=dfs(t,flow_limit-flow)
                if not(f):
                    break
                flow+=f
            return flow
        
        def min_cut(s):
            visited=[False for i in range(self.n)]
            que=deque([])
            que.push(s)
            while(len(que)>0):
                p=que.popleft()
                visited[p]=True
                for e in g[p]:
                    if e[2] and not(visited[e[0]]):
                        visited[e[0]]=True
                        que.append(e[0])
            return visited

N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
G=mf_graph(N*M+2)
D=[[(i*N+j+1) for j in range(M)] for i in range(N)]
di=[1,0,-1,0]
dj=[0,1,0,-1]
for i in range(N):
    for j in range(M):
        if S[i][j]=="#":
            continue
        if (i+j)%2==0:
            G.add_edge(0,i*N+j+1,1)
            for k in range(4):
                ni=i+di[k]
                nj=j+dj[k]
                if 0<=ni<N and 0<=nj<M:
                    if S[ni][nj]==".":
                        G.add_edge(i*N+j+1,ni*N+nj+1,1)
        else:
            G.add_edge(i*N+j+1,N*M+1,1)
G.flow(0,N*M+1,(1<<31)-1)
T=[[S[i][j] for j in range(M)] for i in range(N)]
for e in G.edges():
    if e["to"]==N*M+1 or e["from"]==0 or e["flow"]==0:
        continue
    ax=(e["from"]-1)%N
    ay=(e["from"]-1)//N
    bx=(e["to"]-1)%N
    by=(e["to"]-1)//N
    if ax==bx:
        if ay<by:
            T[by][bx]="^"
            T[ay][ax]="v"
        else:
            T[ay][ax]="^"
            T[by][bx]="v"
    else:
        if ax<bx:
            T[by][bx]="<"
            T[ay][ax]=">"
        else:
            T[ay][ax]="<"
            T[by][bx]=">"

for ans in T:
    print("".join(ans))

Buggy submission (verdict: Runtime Error):
from collections import deque
class mf_graph():
    n=1
    g=[[] for i in range(n)]
    pos=[]
    def __init__(self,N):
        self.n=N
        self.g=[[] for i in range(N)]
    def add_edge(self,f,t,cap):
        assert 0<=f<self.n, "0<=from<n,(from,n)=({0},{1})".format(f,self.n)
        assert 0<=t<self.n, "0<=to<n,(to,n)=({0},{1})".format(t,self.n)
        assert 0<=cap, "cap must be not negative,cap={0}".format(cap)
        m=len(self.pos)
        self.pos.append((f,len(self.g[f])))
        self.g[f].append((t,len(self.g[t]),cap))
        self.g[t].append((f,len(self.g[f])-1,0))
        return m
    def get_edge(self,i):
        m=len(self.pos)
        assert 0<=i<m, "0<=i<len(pos)=m,(i,m)=({0},{1})".format(i,m)
        e=self.g[self.pos[i][0]][self.pos[i][1]]
        re=self.g[e[0]][e[1]]
        return (self.pos[i][0],e[0],e[2]+re[2],re[2])
    def edges(self):
        m=len(self.pos)
        result=[]
        for i in range(m):
            result.append(self.get_edge(i))
        return result
    def change_edge(self,i,new_cap,new_flow):
        m=len(self.pos)
        assert 0<=i<m,"0<=i<len(pos)=m,(i,m)=({0},{1})".format(i,m)
        assert 0<=new_flow and new_flow<=new_cap, "0<=new_flow<=new_cap,(new_flow,new_cap)=({0},{1})".format(new_flow,new_cap)
        eto,erev,ecap=self.g[self.pos[i][0]][self.pos[i][1]]
        reto,rerev,recap=self.g[eto][erev]
        self.g[self.pos[i][0]][self.pos[i][1]]=(eto,erev,new_cap-new_flow)
        self.g[eto][erev]=(reto,rerev,new_flow)
    #edge : (from,to,cap,flow)
    #g in _edge
    #_edge : (to,rev,cap)
    def flow(self,s,t,flow_limit):
        assert 0<=s<self.n, "0<=s<n,(s,n)=({0},{1})".format(s,self.n)
        assert 0<=t<self.n, "0<=t<n,(t,n)=({0},{1})".format(t,self.n)
        level=[0 for i in range(self.n)]
        iter0=[0 for i in range(self.n)]
        que=deque([])
        def bfs():
            level=[-1 for i in range(self.n)]
            que=deque([])
            que.append(s)
            while(len(que)>0):
                v=que.popleft()
                for e in self.g[v]:
                    if e[2]==0 or level[e[0]]>=0:
                        continue
                    level[e[0]]=level[v]+1
                    if e[0]==t:
                        return
                    que.append(e[0])
        def dfs(v,up):
            if v==s:
                return up
            res=0
            level_v=level[v]
            for i in range(iter0[v],len(self.g[v])):
                e=self.g[v][i]
                if level_v<=level[e[0]] or self.g[e[0]][e[1]][2]==0:
                    continue
                d=dfs(e[0],min(up-res,self.g[e[0]][e[1]][2]))
                if d<=0:
                    continue
                self.g[v][i]=(self.g[v][i][0],self.g[v][i][1],self.g[v][i][2]+d)
                self.g[e[0]][e[1]]=(self.g[e[0]][e[1]][0],self.g[e[0]][e[1]][1],self.g[e[0]][e[1]][2]-d)
                res+=d
                if res==up:
                    break
            return res
        flow=0
        while(flow<flow_limit):
            bfs()
            if level[t]==-1:
                break
            iter0=[0 for i in range(self.n)]
            while(flow<flow_limit):
                f=dfs(t,flow_limit-flow)
                if not(f):
                    break
                flow+=f
            return flow
        
        def min_cut(s):
            visited=[False for i in range(self.n)]
            que=deque([])
            que.push(s)
            while(len(que)>0):
                p=que.popleft()
                visited[p]=True
                for e in g[p]:
                    if e[2] and not(visited[e[0]]):
                        visited[e[0]]=True
                        que.append(e[0])
            return visited

N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
G=mf_graph(N*M+2)
D=[[(i*N+j+1) for j in range(M)] for i in range(N)]
di=[1,0,-1,0]
dj=[0,1,0,-1]
for i in range(N):
    for j in range(M):
        if S[i][j]=="#":
            continue
        if (i+j)%2==0:
            G.add_edge(0,i*N+j+1,1)
            for k in range(4):
                ni=i+di[k]
                nj=j+dj[k]
                if 0<=ni<N and 0<=nj<M:
                    if S[ni][nj]==".":
                        G.add_edge(i*N+j+1,ni*N+nj+1,1)
        else:
            G.add_edge(i*N+j+1,N*M+1,1)
G.flow(0,N*M+1,(1<<31)-1)
T=[[S[i][j] for j in range(M)] for i in range(N)]
for e in G.edges():
    if e[1]==N*M+1:
        continue
    if e[0]==0:
        continue
#    if e[3]==0:
#        continue
    ax=(e[0]-1)%N
    ay=(e[0]-1)//N
    bx=(e[1]-1)%N
    by=(e[1]-1)//N
    if ax==bx:
        if ay<by:
            T[by][bx]="^"
            T[ay][ax]="v"
        else:
            T[ay][ax]="^"
            T[by][bx]="v"
    else:
        if ax<bx:
            T[by][bx]="<"
            T[ay][ax]=">"
        else:
            T[ay][ax]="<"
            T[by][bx]=">"

for ans in T:
    print("".join(ans))