CODE FESTIVAL 2017 qual B C - 3 Steps

解答

code: python

import sys

sys.setrecursionlimit(100000)

from collections import defaultdict

G = defaultdict(list)

N, M = map(int, input().split())

visited = [False for i in range(N) for j in range(5)]

for i in range(M):

v,u = map(int, input().split())

Gv-1.append(u-1)

Gu-1.append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ判定をする

def dfs(pos, color):

global COLOR

COLORpos = color

ans = True

for to in Gpos:

# 同じ色が隣接

if COLORto == color:

return False

elif COLORto == 0:

ans &= dfs(to, -color)

return ans

if dfs(0, 1):

count = 0

for i in COLOR:

if i == -1:

count += 1

another = N-count

print(count*another-M)

else:

# 2 部グラフではなかったので、完全グラフから M を引いた値を出力する

print(N*(N-1)//2-M)

テーマ

メモ