Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <queue>
- #include <vector>
- #include <iostream>
- #include <set>
- #include <map>
- #include <cmath>
- #include <algorithm>
- #include <stdlib.h>
- #include <cstdio>
- using namespace std;
- typedef long long LL;
- /*
- таймер, для быстрого использования массива used(избегания прохода и очистки, мы просто делаем timer++ и когда хотим узнать использована ли вершина сравниваем used[x]
- не с 0 или 1, как делали бы раньше, а с timer)
- */
- int timer = 1;
- vector<vector<int> > g;//список смежности графа
- vector<int> used;//вектор использованных вершин
- //dfs_size - рекурсивно считает размер компоненты связности, ставя для каждой вершины used = timer
- int dfs_size(int v)
- {
- int ret = 1;
- used[v] = timer;
- for (int i = 0; i < g[v].size(); i++)
- {
- int to = g[v][i];
- if (used[to] != timer)
- ret += dfs_size(to);
- }
- return ret;
- }
- int main()
- {
- freopen("INPUT.TXT", "r", stdin);
- freopen("OUTPUT.TXT", "w", stdout);
- int n, m;//количество вершин и ребер
- cin >> n >> m;
- g.resize(n);
- used.assign(n, 0);
- for (int i = 0; i < m; i++)
- {
- int a, b;
- cin >> a >> b;
- a--, b--;//ведем нумерацию с 0
- //добавляем ребра в список смежности
- g[a].push_back(b);
- g[b].push_back(a);
- }
- for (int i = 0; i < n; i++)
- {
- vector<int> sizes;//массив размеров компонент связностей, на которые разобьется наша компонента, если мы удалим ребра ведущие из вершины i
- timer++;
- used[i] = timer;//помечаем текущую вершину использованной, чтобы не заходить в нее в dfs_size
- for (int j = 0; j < g[i].size(); j++)
- {
- int to = g[i][j];//to - вершина, в которую мы можем пойти из нашей
- //если мы в ней еще не были, значит used[to] != timer и мы можем в нее пойти и записать размер ее компоненты связности в массив sizes
- if (used[to] != timer)
- sizes.push_back(dfs_size(to));
- }
- //ans - ответ для текущей вершины i, all_sum - сумма всех размеров компонент связностей из массива sizes
- LL ans = 0, all_sum = 0;
- //считаем all_sum
- for (int j = 0; j < sizes.size(); j++)
- all_sum += sizes[j];
- ans = all_sum;//здесь учитываем все вершины, когда наша вершина сама является одной из пары (B,C)
- //вычисляем ответ для нашей вершины, по комбинаторной формуле
- /*
- Пусть у нас есть 4 компоненты, их размеры
- A, B, C, D
- Тогда при любом соединении 2х вершин из разных компонент, их путь точно будет лежать через нашу вершину, иначе они бы не были в разных компонентах.
- Соединив любую вершину из A с любой вершиной из B, C, D мы получим A(B+C+D) связей или A(all_sum - A) связей.
- Соединив любую вершину из B с любой вершиной из C и D(не будет соединять с A, т.к. тогда посчитаем некоторые связи дважды), мы получим B(C + D) связей или B(all_sum - A - B) связей.
- Соединив любую вершину из C с любой вершиной из D(не будем соединять с вершинами из A и B по той же причине), мы получим C(D) связей или C(all_sum - A - B - C) связей.
- Сложив все результаты полученные раньше мы получим ответ для нашей вершины, т.к. учли все связи
- Давайте и сделаем это
- */
- for (int j = 0; j < sizes.size(); j++)
- {
- all_sum -= sizes[j];
- ans += sizes[j] * (all_sum);
- }
- cout << ans << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement