Решение алгоритма графа сделано правильно?

Question

Я наткнулся на проблему с последней Кубка Facebook Hacker Cup (так что это НЕ моя домашняя работа, я просто нахожу ее очень интересной), и я также подумал о любопытном, но довольно хорошем решении.Не могли бы вы проверить мою мысль?Вот задача:

Вам предоставлена ​​сеть из N городов и М двунаправленных дорог, соединяющих эти города.Первые K городов важны.Необходимо удалить минимальное количество дорог, чтобы в оставшейся сети не было циклов, содержащих важные города.Цикл - это последовательность, по крайней мере, трех разных городов, так что каждая пара соседних городов соединена дорогой, а первый и последний города в последовательности также соединены дорогой.

Ввод
В первой строке содержится количество тестовых случаев T.

Каждый случай начинается со строки, содержащей целые числа N, M и K, которые представляют количество городов, количество дорог иколичество важных городов соответственно.Города пронумерованы от 0 до N-1, а важные города пронумерованы от 0 до K-1.Следующие M строк содержат два целых числа a [i] и b [i], 0 ≤ i

Гарантируется, что 0 ≤ a [i],b [i]

Вывод
Для каждого из тестовых случаев, пронумерованных в порядке от 1 до T, выведите «Case #i:», а затемодно целое число, минимальное количество дорог, которые необходимо удалить, чтобы не было циклов, содержащих важный город.

Ограничения
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ K ≤ N

Пример
В первом примере мы имеем N = 5 городов, которыесоединены М = 7 дорогами и города 0 и 1 важны.Мы можем удалить две дороги, соединяющие (0, 1) и (1, 2), и оставшаяся сеть не будет содержать циклы с важными городами.Обратите внимание, что в оставшейся сети есть цикл, который содержит только не важные города, и что есть также несколько способов удалить две дороги и удовлетворить все условия.Нельзя удалить только одну дорогу и уничтожить все циклы, которые содержат важные города.

Пример ввода
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4

Поэтому я подумал об этом так: при построении графика давайтемассив, хранящий информацию о том, сколько соседей имеет каждый город (== сколько дорог там связано с данным городом).В этом примере у города 0 2, у города 1 3 и т. Д.Давайте назовем эти числа «значением города» определенного города.

После получения всего ввода мы проходим весь массив значений городов в поисках городов со значением 1. При переходе к одному это означает, чтоне может быть в цикле, поэтому мы уменьшаем его значение, «удаляем» (без потери общности) дорогу, соединяющую его со своим единственным соседом, и уменьшаем значение соседа.После этого мы рекурсивно идем к соседу, проверяя ту же вещь, если значение там 1 - повторяем схему и рекурсивно идем глубже.Если нет - не трогай.

После этой оперыКроме того, мы очистили все части графика, которые не являются циклами и не могут быть их частью. Мы также избавились от всех дорог, которые не имели смысла. Так что на этот раз мы называем другую функцию - работаем только в важных городах. Итак, мы берем вершину 1 - после использования функции, описанной в предыдущем абзаце, ее значение не может быть 1 (так как она уже была бы сделана нулем функцией), поэтому либо 0, либо что-то> 1. В первом случае нам не нужно ничего делать. В последнем случае мы должны сделать значение 1, которое выполняется удалением значения-1. Как и в предыдущем абзаце, после каждого удаления мы уменьшаем значение как этого города, так и его соседа, также удаляя дорогу. Мы повторяем это для всех k важных городов, суммируя значения 1 из всех важных городов, и это наш ответ.

Есть ли смысл? Для всех тестов, которые я пробовал, это работало, и я хотел бы верить, что это правильно, но я почему-то чувствую, что где-то может быть утечка. Не могли бы вы проверить это? Это хорошо? Если нет, то почему в этом мыслительном процессе что-то правильно? :)

Answer 1

Здесь было неправильное решение.

Контрпример для вашего решения.Предположим, что один в квадрате является единственным важным.Ваше решение удалит одну дорогу.

Answer 2

Если вы можете доказать, что оптимальное количество срезов равно количеству различных циклов *, которые содержат важный узел, решить проблему не так сложно.

Вы можете создавать DFS, отслеживать посещенные узлы, и всякий раз, когда вы достигаете узла, который уже посетили, вы получаете цикл. Чтобы определить, содержит ли цикл важный узел или нет, отследите глубину, на которой был посещен каждый узел, и запомните глубину последнего важного узла в текущей ветви поиска. Если начальная глубина цикла меньше (то есть раньше) глубины последнего важного узла, цикл содержит важный узел.

C ++ реализация:

// does not handle multiple test cases

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 10000;

int n, m, k;
vector<int> edges[MAX];
bool seen[MAX];
int seenDepth[MAX]; // the depth at which the DFS visited the node

bool isImportant(int node) { return node < k; }

int findCycles(int node, int depth, int depthOfLastImp)
{
    if (seen[node])
    {
        if (seenDepth[node] <= depthOfLastImp && (depth - seenDepth[node]) > 2)
        {
            // found a cycle with at least one important node
            return 1;
        }
        else
        {
            // found a cycle, but it's not valid, so cut this branch
            return 0;
        }
    }
    else
    {
        // mark this node as visited
        seen[node] = true;
        seenDepth[node] = depth;

        // recursively find cycles
        if (isImportant(node)) depthOfLastImp = depth;
        int cycles = 0;
        for (int i = 0; i < edges[node].size(); i++)
        {
            cycles += findCycles(edges[node][i], depth + 1, depthOfLastImp);
        }
        return cycles;
    }
}

int main()
{
    // read data
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int start, stop;
        cin >> start >> stop;
        edges[start].push_back(stop);
        edges[stop].push_back(start);
    }

    int numCycles = 0;
    for (int i = 0; i < m; i++)
    {
        if (!seen[i])
        {
            // start at depth 0, and last important was never (-1)
            numCycles += findCycles(i, 0, -1);
        }
    }

    cout << numCycles << "\n";
    return 0;
}

---

* Под «другим» я подразумеваю, что цикл не считается, если все его ребра уже являются частью разных циклов. В следующем примере я считаю количество циклов 2, а не 3:

    A–B
    | |
    C–D
    | |
    E–F

Answer 3

Мой алгоритм основан на следующем наблюдении: поскольку нам не нужны циклы с неважными узлами, неважными узлами могут быть свернуты.Мы сворачиваем два соседних неважных узла, заменяя их одним неважным узлом с суммой ребер из исходных узлов.

При свертывании двух неважные узлы, нам нужно обработать два особых случая:

1. Оба узла были подключены к одному и тому же неважным узлу U .Это означает, что в исходном графе был цикл неважных узлов;мы можем игнорировать цикл, и новый узел будет связан с тем же неважным узлом U с одним ребром.
2. Оба узла были подключены к одному и тому же важному узлу I .Это означает, что в исходном графе был цикл неважных узлов и один важный узел I ;перед свертыванием узлов нам нужно удалить одно из ребер, соединяющее их с важным узлом I и, таким образом, удалить цикл;Новый узел будет связан с важным узлом I с одним ребром.

С приведенным выше определением свертывания узла алгоритм имеет следующий вид:

1. Сохраняйте коллапс соседних неважных узлов, пока не будет соседних неважных узлов.Все удаленные ребра между важными и неважными узлами, как определено в случае (2) выше, учитываются для решения.
2. Найдите остовное дерево оставшегося графа иудалите все ребра, которые не включены в связующее дерево.Все ребра, удаленные на этом этапе, учитываются в решении.

Алгоритм выполняется за время O (M).Я верю, что могу доказать его правильность, но хотел бы получить ваш отзыв, прежде чем я потрачу на это слишком много времени: -)