Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.41 KB | None | 0 0
  1. #include <string>
  2. #include <queue>
  3. #include <vector>
  4. #include <iostream>
  5. #include <set>
  6. #include <map>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <stdlib.h>
  10. #include <cstdio>
  11.  
  12. using namespace std;
  13. typedef long long LL;
  14. /*
  15. таймер, для быстрого использования массива used(избегания прохода и очистки, мы просто делаем timer++ и когда хотим узнать использована ли вершина сравниваем used[x]
  16. не с 0 или 1, как делали бы раньше, а с timer)
  17. */
  18. int timer = 1;
  19. vector<vector<int> > g;//список смежности графа
  20. vector<int> used;//вектор использованных вершин
  21. //dfs_size - рекурсивно считает размер компоненты связности, ставя для каждой вершины used = timer
  22. int dfs_size(int v)
  23. {
  24. int ret = 1;
  25. used[v] = timer;
  26. for (int i = 0; i < g[v].size(); i++)
  27. {
  28. int to = g[v][i];
  29. if (used[to] != timer)
  30. ret += dfs_size(to);
  31. }
  32. return ret;
  33. }
  34. int main()
  35. {
  36. freopen("INPUT.TXT", "r", stdin);
  37. freopen("OUTPUT.TXT", "w", stdout);
  38. int n, m;//количество вершин и ребер
  39. cin >> n >> m;
  40. g.resize(n);
  41. used.assign(n, 0);
  42. for (int i = 0; i < m; i++)
  43. {
  44. int a, b;
  45. cin >> a >> b;
  46. a--, b--;//ведем нумерацию с 0
  47. //добавляем ребра в список смежности
  48. g[a].push_back(b);
  49. g[b].push_back(a);
  50. }
  51. for (int i = 0; i < n; i++)
  52. {
  53. vector<int> sizes;//массив размеров компонент связностей, на которые разобьется наша компонента, если мы удалим ребра ведущие из вершины i
  54. timer++;
  55. used[i] = timer;//помечаем текущую вершину использованной, чтобы не заходить в нее в dfs_size
  56. for (int j = 0; j < g[i].size(); j++)
  57. {
  58. int to = g[i][j];//to - вершина, в которую мы можем пойти из нашей
  59. //если мы в ней еще не были, значит used[to] != timer и мы можем в нее пойти и записать размер ее компоненты связности в массив sizes
  60. if (used[to] != timer)
  61. sizes.push_back(dfs_size(to));
  62. }
  63. //ans - ответ для текущей вершины i, all_sum - сумма всех размеров компонент связностей из массива sizes
  64. LL ans = 0, all_sum = 0;
  65. //считаем all_sum
  66. for (int j = 0; j < sizes.size(); j++)
  67. all_sum += sizes[j];
  68. ans = all_sum;//здесь учитываем все вершины, когда наша вершина сама является одной из пары (B,C)
  69. //вычисляем ответ для нашей вершины, по комбинаторной формуле
  70. /*
  71. Пусть у нас есть 4 компоненты, их размеры
  72. A, B, C, D
  73. Тогда при любом соединении 2х вершин из разных компонент, их путь точно будет лежать через нашу вершину, иначе они бы не были в разных компонентах.
  74. Соединив любую вершину из A с любой вершиной из B, C, D мы получим A(B+C+D) связей или A(all_sum - A) связей.
  75. Соединив любую вершину из B с любой вершиной из C и D(не будет соединять с A, т.к. тогда посчитаем некоторые связи дважды), мы получим B(C + D) связей или B(all_sum - A - B) связей.
  76. Соединив любую вершину из C с любой вершиной из D(не будем соединять с вершинами из A и B по той же причине), мы получим C(D) связей или C(all_sum - A - B - C) связей.
  77. Сложив все результаты полученные раньше мы получим ответ для нашей вершины, т.к. учли все связи
  78. Давайте и сделаем это
  79. */
  80. for (int j = 0; j < sizes.size(); j++)
  81. {
  82. all_sum -= sizes[j];
  83. ans += sizes[j] * (all_sum);
  84. }
  85. cout << ans << "\n";
  86. }
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement