fork(3) download
copy 
  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
comments (?)
stdin
copy 
4 4
1  2
    2  3
    3  4
    4 1
stdout
copy 
3 4
https://ideone.com/PfnqgU
Путешествия в космосе
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

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!