Problem p03409 (python)

Fixed submission:
from collections import deque


class Dinic:

    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        self.level = level
        return level[1] is not None

    def dfs(self, v, t):
        if v == t:
            return 1
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w] and self.dfs(w, t):
                e[1] = 0
                rev[1] = 1
                return 1
        return 0

    def flow(self):
        flow = 0
        while self.bfs():
            *self.it, = map(iter, self.G)
            while self.dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

#####################################################################################

N = int(input())
s = []
ss = []
for i in range(N):
    s.append([int(i) for i in input().split()])

for i in range(N):
    ss.append([int(i) for i in input().split()])

pair = []
for i in range(len(s)):
    right = []
    for j in range(N):
        if s[j][0] < ss[i][0] and s[j][1] < ss[i][1]:
            right.append(j)
    pair.append(right)

# print(pair)

#####################################################################################


# 頂点の組u,vと辺の重みc（今回は1）からグラフ作って最大流で解くFOOOOOOOOOOOOOOOOO

V = len(pair) + N + 2  # (sとt追加)

dinic = Dinic(V, V)

for i in range(len(pair)):  # 始点s（番号0）から青い点(1から最大len(pair))への辺
    u, v, c = 0, i + 1, 1
    dinic.add_edge(u, v)

for i in range(N):  # 赤い点（len(pair)+1から最大len(pair)+n）から終点t（番号V-1）への辺
    u, v, c = i + len(pair) + 1, V - 1, 1
    dinic.add_edge(u, v)

for i in range(len(pair)):  # 青い点（番号1から最大len(pair)に振り直し）から　赤い点（番号1～100に振り直し）への辺
    for j in range(len(pair[i])):
        node1, node2 = i + 1, pair[i][j] + len(pair) + 1

        u, v, c = node1, node2, 1
        dinic.add_edge(u, v)

print(dinic.flow() - 2)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

class Dinic:
    def __init__(self, len_X, len_Y):
        self.len_X, self.len_Y = len_X, len_Y
        self.edges = [[] for _ in range(len_X)]
        self.matched = [-1] * len_Y
        self.visited = set()

    def add_edge(self, x, y):
        self.edges[x].append(y)

    def dfs(self, x):
        """
        :param x: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for next_x in self.edges[x]:
            if next_x in self.visited:
                continue
            self.visited.add(next_x)
            if self.matched[next_x] == -1 or self.dfs(self.matched[next_x]):
                self.matched[next_x] = x
                return True
        return False

    def solve(self):
        """ 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる """
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res

#################################################################################################


len_X, len_Y, E = map(int, input().split())     # len_X, len_Y: 部分集合に含まれる頂点の数　E: 辺の数


dinic = Dinic(len_X, len_Y)

for _ in range(E):
    x, y = map(int, input().split())
    dinic.add_edge(x,y)

print(dinic.solve())

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc091/tasks/arc092_a

import sys
input = sys.stdin.readline
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            """
            :param to:  終点ノード
            :param cap: 残された容量
            :param rev: 遂になる逆向きのエッジ（ノード to の rev 番目のエッジ）
            """
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1] * self._node
        self._iter = [0] * self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

    def bfs(self, start):
        """
        _level: 未訪問の場合は -1, 訪問済みの場合は start からの最短距離（正容量のエッジのみを使った経路の中での）
        """
        self._level = [-1] * self._node
        next_set = deque()
        self._level[start] = 0
        next_set.append(start)
        while next_set:
            cur_vertex = next_set.popleft()
            for edge in self._graph[cur_vertex]:
                if self._level[edge.to] < 0 < edge.cap:
                    self._level[edge.to] = self._level[cur_vertex] + 1
                    next_set.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            edge = self._graph[cur_vertex][self._iter[cur_vertex]]
            if edge.cap > 0 and self._level[cur_vertex] < self._level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self._graph[edge.to][edge.rev].cap += flowed
                    return flowed
            self._iter[cur_vertex] += 1
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                """ sinkへの最短距離が -1 ⇒ sink にたどり着けない ⇒ 増加路が存在しないため探索終了"""
                return flow
            self._iter = [0] * self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class Dinic:
    def __init__(self, len_X, len_Y):
        """
        soursの位置 = 0
        sinkの位置  = len_X + len_Y + 1
        capacity   = 1
        の最大フロー問題
        """
        self.len_X, self.len_Y = len_X, len_Y
        self.mf = MaxFlow(self.len_X + self.len_Y + 2, min(self.len_X, self.len_Y))
        for i in range(self.len_X):
            """ sours から部分集合Xへの各点に capacity=1 の流れを作る """
            self.mf.add_edge(0, i + 1, 1)
        for i in range(self.len_Y):
            """ 部分集合Yへの各点からsinkへの capacity=1 の流れを作る """
            self.mf.add_edge(self.len_X + i + 1, self.len_X + self.len_Y + 1, 1)

    def add_edge(self, from_, to):
        """
        :param from_: 部分集合Xの頂点　（1,...,len_X）
        :param to:    部分集合Yの頂点　（len_X + 1,...,len_X + 1 + len_Y）
        """
        self.mf.add_edge(from_ + 1, to + self.len_X + 1, 1)

    def solve(self):
        return self.mf.solve(0, self.len_X + self.len_Y + 1)

#####################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i,j)


print(dinic.flow())