Problem p03579 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000000)

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)


def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == 0: # まだ塗られていない場合
            if not f(v,-c):
                return False
        else:
            if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
                return False
    return True 

flag = True
color = [0 for _ in range(N)]
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            flag = False
            break

if flag: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)//2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)


def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == 0: # まだ塗られていない場合
            if not f(v,-c):
                return False
        else:
            if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
                return False
    return True 

flag = True
color = [0 for _ in range(N)]
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            flag = False
            break

if flag: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)//2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
            return False
        elif (color[v] ==0 and not f(v,-c)):
            return False
    return True 

bipartite = True
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            bipartite = False

if bipartite: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)/2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
            return False
        elif (color[v] ==0 and not f(v,-c)):
            return False
    return True 

bipartite = True
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            bipartite = False

if bipartite: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
            return False
        elif (color[v] ==0 and not f(graph[v],-c)):
            return False
    return True 

bipartite = True
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            bipartite = False

if bipartite: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(v,c):
    color[v] = c
    for j in range(len(graph[v])):
        if color[ graph[v][j] ] == c: # 隣接している頂点が同色の場合 二部グラフではない
            return False
        elif (color[graph[v][j]] ==0 and not f(graph[v][j],-c)):
            return False
    return True 

bipartite = True
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            bipartite = False

if bipartite: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(v,c):
    color[v] = c
    for i in range(len(graph[v])):
        if color[ graph[v][i] ] ==c:
            return False
        elif (color[graph[v][i]] ==0 and not f(graph[v][i],-c)):
            return False
    return True 

bipartite = True
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            bipartite = False

if bipartite: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

color = [0 for _ in range(N)]

def f(v,c):
    color[v] = c
    for i in range(len(graph[v])):
        if color[ graph[v][i] ] ==c:
            return False
        elif color[graph[v][i]] ==0 and not f(graph[v][i],-c):
            return False
    return True 

k = 1
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            k = -1

if k == 1: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = M*(M-1)/2 - M

print(int(ans))