Найти кол-во вершин таких что есть путь из а в b проходящий через вершину c

[kjifhfezhf]

Вот условие:

Ограничение по времени: 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;
 
}

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

[MBo]

Поскольку путь не должен быть простым, кажется достаточным получить количество вершин в связном компоненте, содержащем и a[i] и b[i]

[amk]

Если граф неориентированный, то ищем компоненту связности, содержащую заданную вершину. Из любой вершины этой компоненты в любую другую (врочем и в эту самую) можно пройти посетив по пути заданную вершину.
Если граф ориентированный, то придётся искать множество вершин из которых можно попасть в 'c' и множество вершин в которые можно попасть из 'c'. Алгоритм сильно похож на поиск области связности. Из любой вершины первого множества можно попасть в любую вершину второго множества. Этот алгоритм работает и для неориентированных графов, если неориентированное ребро заменить на встречные ориентированные.

Как искать множества достижимости и компоненты связности, объяснять нужно?

[Akina]

Ответил на ruSO.