Каков наиболее эффективный способ получить все поддеревья из массива узлов и вектора ребер?

Question

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

int nodes[n] = {1, 2, 3, ... ,n };
vector<pair<int, int>> edges;

edges.push_back(std::make_pair(0, 2));
edges.push_back(std::make_pair(2, 4));

где каждый элемент массива является значением и nэто номер массива. Следуя приведенному выше коду, есть два ребра. Один от 0 до 2. Другой от 2 до 4. Эти числа указывают индекс массива. В этом случае размер наибольшего поддерева равен 3, что 0-2-4, а размер наименьшего поддерева, очевидно, равен 1.

Я решил это, как показано ниже:

1. Сортировать edges вектор
2. Выберите одну перестановку в edges
3. Повторите 2 до изучения всех возможных случаев

Однако я не уверен, что это эффективный способ. Как я могу получить все поддеревья в проблемной области, как это? Есть ли общий и эффективный способ?

Answer 1

Я решил эту проблему, используя BFS (поиск в ширину) на основе информации о фронте. Чтобы не создавать циклический граф и хранить узлы в виде дерева, я использую set, И я тоже подаю заявку sort перед поиском. Это полезно, чтобы уменьшить сложность времени.

void BFS(set<int> nodes, vector<pair<int,int>>& edges, vector<set<int>>& result) {
    result.push_back(nodes);
    int lastNode = *max_element(nodes.begin(), nodes.end());
    auto findIt = find_if(edges.begin(), edges.end(), [](const pair<int, int>& element){ return element.first == lastNode});
    if(findIt != edges.end()) {
        nodes.insert((*findIt).second);
        BFS(nodes, edges, result);
    }
}

sort(edges.begin(), edges.end());

vector<set<int>> result;
for(auto it : edges) {
    set<int> nodes;
    nodes.insert((*it).first);
    nodes.insert((*it).second);
    BFS(nodes, edges, result);
}