Problem p03579 (python)

Fixed submission:
"""
グラフが二部グラフかどうかを判定する。
二部グラフであれば、AグループのノードとBグループのノード同士をそれぞれ結ぶことができる。
二部グラフでない場合、すべてのノード同士を結ぶことができる。
"""
import math
from collections import Counter
import sys
sys.setrecursionlimit(200000)
def choose(n):
    return math.factorial(n)//(math.factorial(n-2)*math.factorial(2))
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)

colors = [-1]*(N+1)
def f(n,p):
    c = colors[n]
    for v in edges[n]:
        if v != p:
            if colors[v] == -1:
                colors[v] = 1 if c==0 else 0
                f(v,n)
            elif colors[v] == c:
                print(choose(N)-M)
                exit()
colors[1]=0
f(1,0)
count1 = colors.count(0)
count2 = colors.count(1)
print(count1*count2-M)

Buggy submission (verdict: Runtime Error):
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
n = len(edges)
colors = [-1]*(n+1)
def judgeBiGragh(edges):
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    cnt0 = colors.count(0)
    cnt1 = colors.count(1)
    ans = cnt0*cnt1 - M
else:
    ans = choose(N,2)-M

print(ans)

Buggy submission (verdict: Runtime Error):
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
def judgeBiGragh(edges):
    n = len(edges)
    colors = [-1]*(n+1)
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    ans = (N//2)*(N-N//2) - M
else:
    ans = choose(N,2)-M

print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)

colors = [-1]*(N+1)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
def dfs(n,c):
    if colors[n] == -1:
        colors[n] = c
        for nx in edges[n]:
            dfs(nx,(c+1)%2)
    else:
        if colors[n] != c:
            print(choose(N,2)-M)
            exit()
dfs(1,0)
white = colors.count(0)
black = N - white
print(white*black-M)

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(2000000)

    N,M = map(int,input().split())
    edges = [[]for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)

    colors = [-1]*(N+1)
    def paint(n,p,c):
        ret = 1
        if colors[n]!=-1 and colors[n]!=c:
            ret = 0
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    ret = min(ret,paint(nx,n,(c+1)%2))
        return ret

    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    res = paint(1,0,1)
    if res == 0:
        ans = choose(N,2)-M
    else:
        ans = colors.count(0)*(N-colors.count(0))-M

    print(ans)

main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(200000)

    N,M = map(int,input().split())
    edges = [[]for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)

    colors = [-1]*(N+1)
    def paint(n,p,c):
        ret = 1
        if colors[n]!=-1 and colors[n]!=c:
            ret = 0
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    ret = min(ret,paint(nx,n,(c+1)%2))
        return ret

    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    res = paint(1,0,1)
    if res == 0:
        ans = choose(N,2)-M
    else:
        ans = colors.count(0)*(N-colors.count(0))-M

    print(ans)

main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(200000)

    N,M = map(int,input().split())
    edges = [[]for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)

    colors = [-1]*(N+1)
    def paint(n,p,c):
        ret = 1
        if colors[n]!=-1 and colors[n]!=c:
            ret = 0
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    ret = min(ret,paint(nx,n,(c+1)%2))
        return ret

    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    res = paint(1,0,1)
    if res == 0:
        ans = choose(N,2)-M
    else:
        ans = colors.count(0)*(N-colors.count(0))-M

    print(ans)

main()

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

colors = [-1]*(N+1)
def paint(n,p,c):
    ret = 1
    if colors[n]!=-1 and colors[n]!=c:
        ret = 0
    else:
        colors[n] = c
        for nx in edges[n]:
            if nx != p:
                ret = min(ret,paint(nx,n,(c+1)%2))
    return ret

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
res = paint(1,0,1)
if res == 0:
    ans = choose(N,2)-M
else:
    ans = colors.count(0)*(N-colors.count(0))-M

print(ans)