fork(2) download
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int inspect(int vertice, vector<int> graph[], bool visited[]);
  7. bool allVisited(bool visited[], int n);
  8. int firstNotVisited(bool visited[], int n);
  9.  
  10. int main() {
  11. int n, m, a, b;
  12. cin >> n >> m;
  13.  
  14. vector<int> graph[n] = {};
  15.  
  16. //Ввод данных, создание списка смежности графа
  17.  
  18. for (int i = 0; i < m; i++) {
  19. cin >> a >> b;
  20. a--, b--;
  21. graph[a].push_back(b);
  22. graph[b].push_back(a);
  23. }
  24.  
  25. //Поиск наиболее популярного узла(планеты)
  26. //Осуществляется с помощью Depth-first search, поочередно убирая каждый узел
  27. //и перемножая кол-во планет в получившихся структурах графа
  28.  
  29. int maxPop = 0, maxPlanets = 0;
  30. for (int i = 0; i < n; i++) {
  31. bool visited[n] = {};
  32. //Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе
  33. visited[i] = true;
  34. vector<int> structures;
  35. //Рекурсивно проходим по всему графу, пока остаются непосещенные узлы
  36. //Кол-во итераций = кол-во структур
  37. while (!allVisited(visited, n))
  38. structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));
  39. int pop = n - 1;
  40. //Изначальная популярность - кол-во других планет, т.к. перелет
  41. //между ними и убранной планетой уже не возможен
  42. for (int j = 0; j < structures.size() - 1; j++)
  43. for (int k = j + 1; k < structures.size(); k++)
  44. pop += structures[j] * structures[k];
  45. //Поочередно перемножаем кол-во планет из каждой структуры
  46. if (pop > maxPop) {
  47. maxPlanets = 1;
  48. maxPop = pop;
  49. } else if (pop == maxPop)
  50. maxPlanets++;
  51. }
  52. cout << maxPop << " " << maxPlanets;
  53. }
  54.  
  55. bool allVisited(bool visited[], int n) {
  56. for (int i = 0; i < n; i++)
  57. if (!visited[i]) return false;
  58. return true;
  59. }
  60.  
  61. int firstNotVisited(bool visited[], int n) {
  62. for (int i = 0; i < n; i++)
  63. if (!visited[i]) return i;
  64. return -1;
  65. }
  66.  
  67. int inspect(int vertice, vector<int> graph[], bool visited[]) {
  68. //Рекурсивный метод обхода графа
  69. //Проходится по всем смежным узлам из списка смежности, пока не наткнется
  70. //на уже посещенный узел
  71. int cnt = 1;
  72. visited[vertice] = true;
  73. for (auto e: graph[vertice])
  74. if (!visited[e])
  75. cnt += inspect(e, graph, visited);
  76. return cnt;
  77. }
Success #stdin #stdout 0s 4404KB
stdin
4 4
1  2
    2  3
    3  4
    4 1
stdout
3 4