1

Вот условие:

Ограничение по времени: 2 сек

Вам дан неориентированный граф с n вершинами и m ребрами, не содержащий петель и кратных ребер. Так же вам дано несколько пар вершин (a[i], b[i]). Для каждой пары требуется найти количество вершин c, таких, что существует путь из a[i] в b[i], проходящий через вершину c.

Путь из a в b -- это последовательность вершин, начинающаяся в a и заканчивающаяся в b, такая, что каждые две соседние вершины этой последовательности соединены ребром. Обратите внимание, что путь может проходить по одной и той же вершине более одного раза.

В первой строке через пробел записаны два целых числа n и m (1<= n <= 100;0 <= m <= (n(n−1))/2) --- количество вершин и ребер графа. В следующих m строчках записано по два целых числа u и v (1 <= u,v <= n; u != v) --- номера вершин, которые соединяет описываемое ребро.

В следующей строке записано единственное целое число q (1 <= q <= 5000) --- количество пар (a[i]b[i]). В следующих q строках описываются пары. В i-й из этих строк через пробел записаны целые числа a[i] и b[i] (a[i] != b[i]; 1 <= a[i],b[i] <= n).

Для каждой описанной пары выведите на отдельной строке единственное число --- количество вершин c, таких, что существует путь из a[i] в b[i], проходящий через c.

Сделал эту задачу, путём простого нахождения циклов. Пробовал её решать способом нахождения всех путей и вставки этих вершин в нужный массив. Итого размер этого массива = кол-ву нужных вершин. Но этот способ не заработал, как по времени, так по правильности. Самое лучшее, что я мог сделать - это по циклам - 27/37 тестов.

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>

using namespace std;

ifstream in ("input.txt");
ofstream out ("output.txt");

int n, m, q, finish, start;
bool flag = false;
vector<vector<int>> graph, matrix; //Матрица нужна, чтобы задача шла по времени
vector<int> color, path;
set<int> nodes;

void initialize () {
  graph.resize(n);
  matrix.resize(n, vector<int>(n));
  color.resize(n, 0);
}

void readGraph () {
  for (int i = 0; i < m; i++) {
    int from, to;
    in >> from >> to;
    graph[from-1].push_back(to-1);
    graph[to-1].push_back(from-1);
  }
}

void dfs (int nodeCur, int nodeParent) {
  color[nodeCur] = 1;
  path.push_back(nodeCur);
  for (auto v : graph[nodeCur]) {
    if (v == nodeParent || color[v] == 2) { //Если вершина равна предыдущей или мы в ней уже побывали
      continue;
    }
    if (v == finish) { // Если нашли финиш, то вставляем весь путь в nodes
      nodes.emplace(v);
      nodes.insert(path.begin(), path.end());
      flag = true; //Помечаем, что путь между start и finish точно есть (это нужно, чтобы, в случае, если граф несвязный, выдать нужный результат
    }
    if (color[v] == 1) { //Если мы наткнулись на цикл, значит через все вершины в массиве path можно проложить путь
      nodes.emplace(v);
      for (auto it = path.rbegin(); it != path.rend(); it++) {
        nodes.emplace(*it);
        if (*it == v) {
          break;
        }
      }
    } else {
      dfs(v, nodeCur);
    }
  }
  path.pop_back();
  color[nodeCur] = 2;
}

int fillMatrix () {
  if (matrix[start][finish]) {  //Если мы уже вычислили значение для этой пары, то возвращаем его же
    return matrix[start][finish];
  }
  dfs(start, -1);
  if (!flag) {
    return 0;
  }
  //for_each(nodes.begin(), nodes.end(), [](int a) {out << a+1 << ' ';});
  //out << endl;
  for (int v : nodes) {
    matrix[start][v] = nodes.size(); //Тут подобрать слова сложно, но, думаю, вам итак понятно
  }
  //matrix[start][finish] = nodes.size();
  return matrix[start][finish];
}

void solve () {
  in >> q;
  for (int i = 0; i < q; i++) {
    int from, to;
    in >> from >> to;
    start = from-1;
    finish = to-1;
    int ans = fillMatrix();
    out << ans << endl;
    flag = false;
    nodes.clear();
    color.assign(n, 0);
    path.clear();
  }
}

int main() {
  in >> n >> m;
  initialize();
  readGraph();
  solve();
  /*
  for (auto mas : matrix) {
    copy(mas.begin(), mas.end(), ostream_iterator<int>(out, " "));
    out << endl;
  }
  */
  return 0;

}

Код решения для меня писать вовсе не обязательно, достаточно правильной идеи.

13
  • Не нужно оправдывать свою лень проблемами форматирования. Пишите текстом. А скрин можно приложить на случай несостыковок.
    – KoVadim
    30 мар 2017 в 9:42
  • Без проблем. Если людям так легче, могу переписать вручную.
    – user242423
    30 мар 2017 в 9:43
  • Не думаю что кто-то будет изучать большой фрагмент кода и искать у вас ошибку.
    – nick_n_a
    30 мар 2017 в 9:43
  • В том то и дело, что ошибки вроде как нет, я проверял на многих графах. Просто у меня такое чувство, что сама идея неправильная.
    – user242423
    30 мар 2017 в 9:44
  • Для каждой пары вершин выполняется поиск всех путей в графе (стандартная задача, сто раз обсосанная), и затем делается подсчёт количества уникальных вершин в совокупности этих путей.
    – Akina
    30 мар 2017 в 9:48

1 ответ 1

0

Задача оказалась с подвохом. И тривиальным решением. Процитирую необходимое для понимания сути:

  1. Важное условие

неориентированный граф

  1. Задание

путь из a[i] в b[i], проходящий через вершину c

  1. Скрытая "упрощалка"

путь может проходить по одной и той же вершине более одного раза.

Если учесть всё это, то задача трансформируется в следующую:

Найти количество вершин, достижимых одновременно и из ai, и из bi.

Почему? пример: имеются 3 вершины (1, 2 и 3) и 2 ребра (1-2 и 2-3). Начало - 2, конец - 3... но ведь ничто не мешает посетить вершину 1, выбрав маршрут 2-1-2-3.

И простейшее решение. Красим граф. Т.е. произвольной вершине присваиваем цвет 1, после чего волной красим все смежные вершины. Если после этого остались неокрашенные, произвольной некрашенной присваиваем цвет 2 и повторяем окраску. И так далее, пока все вершины не получат цвет.

Если ai и bi имеют один и тот же цвет, то требуемое количество точек на 2 меньше общего количества точек этого цвета (т.е. все, кроме начальной и конечной). Если же они разного цвета, то таких точек ноль.

2
  • Да, действительно. Задача решена. Ещё её можно трансформировать в такую: проверить нахождения пары вершин в одной компоненте связности, если да, то вывести кол-во вершин в этой компоненте связности, если нет вывести 0.
    – user242423
    1 апр 2017 в 15:19
  • Ещё её можно трансформировать в такую: проверить нахождения пары вершин в одной компоненте связности Можно. Но с учётом того, что на вход подаётся несколько пар, гораздо выгоднее сначала один раз выполнить всю необходимую предобработку, а потом быстро получать результат для каждой из пар.
    – Akina
    1 апр 2017 в 17:33

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки