Submission #1689375

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

int N, M;
bool edge[11][11];
bool used[11], vis[11];
int ans;

void bfs(int n, int s) {
  queue<P> next;
  P cur = P(n, 0);
  next.push(cur);

  while (!next.empty()) {
    cur = next.front();
    next.pop();

    int v = cur.first;
    int depth = cur.second;
    used[v] = true;
    if (depth == 2 && !vis[v] && !edge[s][v]) {
      ans++;
      vis[v] = true;
      continue;
    }
    for (int i = 0; i < N; i++) {
      if (used[i]) continue;
      if (!edge[v][i]) continue;
      next.push(P(i, depth + 1));
    }
  }
}

int main() {
  // 入力
  cin >> N >> M;
  int a, b;
  for (int i = 0; i < M; i++) {
    cin >> a >> b;
    a--; b--;
    edge[a][b] = edge[b][a] = true;
  }

  // 各頂点からの幅優先探索で、深さ2のものの個数を数える
  for (int i = 0; i < N; i++) {
    ans = 0;
    fill(used, used + N, false);
    fill(vis, vis + N, false);
    bfs(i, i);
    cout << ans << endl;
  }

  return 0;
}

Submission Info

Judge Result