解説 | Odd and Even Walk

解説

整数組 $(u,v) \ (1 \le u < v \le N)$ を考えます。

頂点 $u$ と頂点 $v$ が異なる連結成分に属する場合、頂点 $u$ から頂点 $v$ へのウォークは存在しないため、整数組 $(u,v)$ は条件を満たしません。

頂点 $u$ と頂点 $v$ が同一の連結成分に属する場合を考えます。

その連結成分が二部グラフである場合、頂点 $u$ から頂点 $v$ へのウォークの長さの偶奇が一意に定まるため、整数組 $(u,v)$ は条件を満たしません。
その連結成分が二部グラフでない場合、整数組 $(u,v)$ は条件を満たします。

以上より、求める答えは、二部グラフでない連結成分について、それぞれの頂点数を $n$ としたときの $\binom{n}{2}$ の総和です。

BFS や DFS を用いて二部グラフの判定と頂点数の計算を行うことで、計算量 $O(N+M)$ でこの問題を解くことができます。

実装例 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> to(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  long long ans = 0;
  vector<int> c(n, -1);
  for (int i = 0; i < n; i++) if (c[i] == -1) {
    bool ok = true;
    int cnt = 0;
    c[i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      cnt++;
      for (int u : to[v]) {
        if (c[u] != -1) {
          if (c[u] == c[v]) ok = false;
          continue;
        }
        c[u] = c[v] ^ 1;
        q.push(u);
      }
    }
    if (!ok) ans += (long long)cnt*(cnt-1)/2;
  }
  
  cout << ans << '\n';
  return 0;
}

実装例 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30from collections import deque

n, m = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  to[a].append(b)
  to[b].append(a)

ans = 0
c = [-1] * n
for i in range(n):
  if c[i] != -1: continue
  ok = True
  cnt = 0
  c[i] = 0
  q = deque([i])
  while q:
    v = q.popleft()
    cnt += 1
    for u in to[v]:
      if c[u] != -1:
        if c[u] == c[v]: ok = False
        continue
      c[u] = c[v] ^ 1
      q.append(u)
  if not ok: ans += cnt*(cnt-1)//2

print(ans)

難易度評価

外部サイトへ移動します

Odd and Even Walk

解説

ユーザー解説