CODE FESTIVAL 2017 qualB C 3 Steps - いろんなことで四苦Hack（仮）

俺ガイルとゲーマーズの最終巻が読めていないえぬわいです。今週は、全然解けてないですね〜。もっと解かないとな〜。

続きです。

ワカンねぇな〜って思って、解説見たら問題の解釈が間違っていたみたい。

思い出した2部グラフの特徴として、 * 同じ色同士への移動は、偶数長でできる。逆に、違う色同士では、奇数でできる。 * 完全2部グラフの辺数は、(同じ色の頂点数)*(違う色の頂点数)。これは、図を描けば明らか。 * 2 部グラフでないグラフは、奇サイクルを含んでいる。これは、前述した通り、同じ色は、偶数になるから。

ここらへんはちゃんと使えるようにならないと解けないような問題だった。解説は、結構わかった。

解説見て実装。

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())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 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)