この問題は、以下の技術を要求しています。いずれも競技プログラミングの上達に欠かせないので、初心者の方は実装例などを参考にしながら練習することを推奨します。

• 二次元配列
• if 文
• 多重 for-loop

まず、頂点 \(i, j\) を結ぶ辺があるかどうかを表す配列 \(\text{adj}_{i, j}\) を用意します。これは \(O(N^2 + M)\) で求めることができます。

次に、 \((a, b, c)\) の組合せを全探索します。このような組は \(\frac{N(N - 1)(N - 2)}{6}\) 通りありますが、今回の問題では \(N \leq 100\) なので、全て調べても実行時間制限に間に合います。先ほどの \(\text{adj}_{i, j}\) を用いて \(a,b\) 間、\(b, c\) 間、\(c, a\) 間全てに辺があるかを調べ、条件を満たすなら答えに \(1\) を加えます。

全体の計算量は \(O(N^3)\) です。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector adj(n, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        adj[u][v] = adj[v][u] = true;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (adj[i][j] and adj[j][k] and adj[k][i]) {
                    ans += 1;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

実装例 (Python)

n, m = map(int, input().split())

adj = [[False] * n for _ in range(n)]

for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  adj[u][v] = True
  adj[v][u] = True

ans = 0

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if adj[i][j] and adj[j][k] and adj[k][i]:
        ans += 1

print(ans)