fork(6) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 3333;
  5.  
  6. int n, m;
  7. int a[N][N], ans[N];
  8. vector <int> adj[N];
  9.  
  10. void bfs(int r) {
  11.     queue <int> q;
  12.     q.push(r);
  13.     while (!q.empty()) {
  14.         int u = q.front(); q.pop();
  15.         for (int v : adj[u]) if (v != r && !a[r][v]) {
  16.             a[r][v] = a[r][u] + 1;
  17.             //cerr << r << " " << v << " " << a[r][v] << "\n";
  18.             q.push(v);
  19.         }
  20.     }
  21. }
  22.  
  23. int main() {
  24. //    freopen("input.in", "r", stdin);
  25.   //  freopen("output.out", "w", stdout);
  26.  
  27.     scanf("%d%d", &n, &m);
  28.     while (m--) {
  29.         int u, v; scanf("%d%d", &u, &v);
  30.         adj[u].push_back(v);
  31.         adj[v].push_back(u);
  32.     }
  33.  
  34.     //bfs(2);
  35.     for (int i = 1; i <= n; ++i) bfs(i);
  36.  
  37.     for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (a[i][j] != 0) {
  38.         int k = log2(a[i][j]);
  39.         k += 1ll << k != a[i][j]; //cerr << i << " " << j << " " << a[i][j] << " " << k << "\n";
  40.         ans[k]++;
  41.     }
  42.     for (int i = 1; i <= n; ++i) {
  43.         printf("%d ", ans[i]);
  44.         if (ans[i] == 0) break;
  45.     }
  46.  
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0s 59536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v7mYOW
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!