fork(5) download
  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
stdin
Standard input is empty
stdout
Standard output is empty