Сколько рёбер добавить?

Ещё одна задачка на графы. На этот раз мы хотим выяснить, какое минимальное количество рёбер нужно добавить к ориентированному плоскому графу, чтобы любая вершина была достижима из заданной вершины x.

Чисто алгоритмически использование вектора векторов (индекс элемента в векторе верхнего уровня служит номером исходной вершины ребра, а значения элементов вектора - это номера целевых вершин, достижимых из заданной, не забываем, что граф ориентирован, путей "назад" по рёбрам нет) здесь может привести к лишней используемой оперативке, подумайте, какой контейнер из STL изначально подошёл бы лучше (собственно, ответ в коде уже есть)?

Для теста использовался вот этот же граф, из которого удалено рёбро между 2 и 3 вершинами, а все остальные рёбра направлены слева направо или сверху вниз (как они проходят, видно из листинга).

Код выполнялся в консоли Visual Studio 2015.

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std;

const int N = 100; //максимальная размерность
int n, x; //количество вершин и исходная вершина
vector <int> g[N]; //исходный граф
vector <pair <int, int> > res; //граф, полученный в результате
bool vis[N]; //были ли посещены вершины при поиске
bool good[N]; //достижимы ли вершины
int cnt;

void addEdge(int u, int v) { //добавить ребро
 g[u].push_back(v);
 res.push_back(pair<int,int>(u,v));
}

void findAllVertices(int v) { //найти все достижимые из v вершины
 good[v] = true;
 for (auto to : g[v]) if (!good[to]) findAllVertices(to);
}

void findCntOfBadVertices(int v) { //Найти количество недостижимых из v вершин
 vis[v] = true;
 cnt++;
 for (auto to : g[v]) if (!vis[to] && !good[to]) findCntOfBadVertices(to);
}

int minimumEdges() { //вернёт минимальное количество недостающих рёбер
 findAllVertices(x); //найти все вершины, достижимые с исходной
 vector <pair <int, int> > val; 
  //сохранить все вершины с их значением cnt (количеством "плохих" вершин, достижимых из данной)
 for (int i = 0; i < n; i++) {
  if (!good[i]) { //если вершина недостижима
   cnt = 0;
   memset(vis, false, sizeof(vis));
   findCntOfBadVertices(i); //найти cnt этой вершины
   val.push_back(make_pair(cnt, i));
  }
 }
 sort(val.begin(), val.end()); //отсортировать недостижимые вершины по неубыванию их cnt
 reverse(val.begin(), val.end());
 int ans = 0; //найти минимальное количество рёбер для добавления
 for (auto it : val) {
  if (!good[it.second]) {
   ans++;
   res.push_back(pair<int, int>(it.first, it.second));
   findAllVertices(it.second);
  }
 }
 return ans;
}

int main() {
 //Задаём количество вершин и исходную вершину для поиска, 
 //нумерация вершин начинается с нуля!
 n = 8, x = 6;

 //Добавляем вершины в граф:
 addEdge(0, 1);
 addEdge(0, 2);
 addEdge(1, 4);
 addEdge(2, 4);
 addEdge(4, 5);
 addEdge(4, 7);
 addEdge(5, 6);
 addEdge(7, 6);
 
 cout << minimumEdges() << " edge(s) for source vertex " << x << endl; //печать ответа
 for (int i = 0; i<res.size(); i++) { //печать полученного графа
  cout << "(" << res[i].first << "," << res[i].second << ") ";
 }
 cin.get();
 return 0;
}

14.02.2019, 13:03 [1925 просмотров]