Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.137.178.133] |
|
Сообщ.
#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; } Код решения для меня писать вовсе не обязательно, достаточно правильной идеи. |
Сообщ.
#2
,
|
|
|
Поскольку путь не должен быть простым, кажется достаточным получить количество вершин в связном компоненте, содержащем и a[i] и b[i]
|
Сообщ.
#3
,
|
|
|
Если граф неориентированный, то ищем компоненту связности, содержащую заданную вершину. Из любой вершины этой компоненты в любую другую (врочем и в эту самую) можно пройти посетив по пути заданную вершину.
Если граф ориентированный, то придётся искать множество вершин из которых можно попасть в 'c' и множество вершин в которые можно попасть из 'c'. Алгоритм сильно похож на поиск области связности. Из любой вершины первого множества можно попасть в любую вершину второго множества. Этот алгоритм работает и для неориентированных графов, если неориентированное ребро заменить на встречные ориентированные. Как искать множества достижимости и компоненты связности, объяснять нужно? |
Сообщ.
#4
,
|
|
|
Ответил на ruSO.
|