Problem p03579 (python)

Fixed submission:
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print(black*white - m)
    else:
        print(int((n-1)*n / 2) - m)

main()

Buggy submission (verdict: Runtime Error):
def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        for i in range(n):
            st = "white" if seen[i] == 0 else "black"
            print(str(i) + ":" + st)
    else:
        print("is not bipartite")

main()

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(1000000)

def triangle(m, g):
    for i in range(m):
        nex_ls = g[i]
        for nex in nex_ls:
            for nex2 in g[nex]:
                if nex2 == i:
                    continue
                if nex2 in nex_ls:
                    return True
    return False


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)

    if triangle(m, g):
        line_max = int((n-1)*n/2)
        print(line_max - m)
    else:
        if n % 2 == 0:
            line_max = int(n*n/4)
            print(line_max - m)
        else:
            line_max = int((n*n - 1)/2)
            print(line_max - m)


main()