Вот условие:
Ограничение по времени: 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;
}
Код решения для меня писать вовсе не обязательно, достаточно правильной идеи.