Problem p03409 (python)

Fixed submission:
N = int(input())

a, b = [], []
for n in range(N):
    _a, _b = map(int, input().split(' '))
    a.append(_a)
    b.append(_b)

c, d = [], []
for n in range(N):
    _c, _d = map(int, input().split(' '))
    c.append(_c)
    d.append(_d)

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

# 標準入力からのグラフ読み取り
edges = [set() for _ in range(N)]
matched = [-1] * N

# 隣接行列
M = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if a[i] < c[j] and b[i] < d[j]:
            edges[i].add(j)

# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(N)))

Buggy submission (verdict: Runtime Error):
def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None


def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)
    

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M

if __name__ == '__main__':
    # print(explanation)
    E = []

    N = int(input())

    a, b = [], []
    for n in range(N):
        _a, _b = map(int, input().split(' '))
        a.append(_a)
        b.append(_b)

    c, d = [], []
    for n in range(N):
        _c, _d = map(int, input().split(' '))
        c.append(_c)
        d.append(_d)

    U0 = [i for i in range(N)]
    V0 = [i for i in range(N)]

    # 隣接行列
    M = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                E.append((i, j))

    # CALC
    edges = Hungary(U0, V0, E)

    # OUTPUT
    print(len(edges))