DFS: Як вказати вузли з'єднаних компонентів у C ++

Алгоритм приблизно такий:

• Отримати вузол графіка.
• Знайти всі вузли, які безпосередньо чи непрямо підключені до нього (в обох напрямках).
• Позначте всі їх як "пройдені" і помістіть їх у новий компонент.
• Знайдіть наступний вузол, який не проходить і повторює процес.

Результатом є набір "компонентних" структур даних ( std :: vector в моїй реалізації), кожен з яких містить набір виключно взаємозв'язаних вузлів.

Міркування:

• Нам потрібно зберігати графік у структурі, яка може ефективно переходити як "вниз" (від батьків до дітей), так і "вгору" (від дітей до батьків) і рекурсивно знаходити всі пов'язані вузли (в обох напрямках), маркування вузлів як "пройдених", як ми йдемо. Оскільки вузли ідентифіковані безперервним діапазоном цілих чисел, ми можемо ефективно побудувати цю структуру лише за допомогою властивостей випадкового доступу std :: vector .
• Поняття ребер і вузлів відокремлені, тому єдиний "прохідний" прапор може існувати на рівні вузла, незалежно від того, скільки інших вузлів підключено до нього (тобто незалежно від того, як є багато батьківських і дочірніх ребер). Це дає змогу ефективно вирізати рекурсію для вже досягнутих вузлів.

Ось робочий код. Зауважимо, що деякі функції C ++ 11 були використані, але їх слід легко замінити, якщо використовується старий компілятор. Обробка помилок залишається як вправа для читача.

#include 
#include 
#include 

// A set of inter-connected nodes.
typedef std::vector Component;

// Graph node.
struct Node {
    Node() : Traversed(false) {
    }
    std::vector Children;
    std::vector Parents;
    bool Traversed;
};

// Recursive portion of the FindGraphComponents implementation.
//   graph: The graph constructed in FindGraphComponents().
//   node_id: The index of the current element of graph.
//   component: Will receive nodes that comprise the current component.
static void FindConnectedNodes(std::vector& graph, unsigned node_id, Component& component) {

    Node& node = graph[node_id];
    if (!node.Traversed) {

        node.Traversed = true;
        component.push_back(node_id);

        for (auto i = node.Children.begin(); i != node.Children.end(); ++i)
            FindConnectedNodes(graph, *i, component);

        for (auto i = node.Parents.begin(); i != node.Parents.end(); ++i)
            FindConnectedNodes(graph, *i, component);

    }

}

// Finds self-connected sub-graphs (i.e. "components") on already-prepared graph.
std::vector FindGraphComponents(std::vector& graph) {

    std::vector components;
    for (unsigned node_id = 0; node_id < graph.size(); ++node_id) {
        if (!graph[node_id].Traversed) {
            components.push_back(Component());
            FindConnectedNodes(graph, node_id, components.back());
        }
    }

    return components;

}

// Finds self-connected sub-graphs (i.e. "components") on graph that should be read from the input stream.
//   in: The input test case.
std::vector FindGraphComponents(std::istream& in) {

    unsigned node_count, edge_count;
    std::cin >> node_count >> edge_count;

   //First build the structure that can be traversed recursively in an efficient way.
    std::vector graph(node_count);//Index in this vector corresponds to node ID.
    for (unsigned i = 0; i < edge_count; ++i) {
        unsigned from, to;
        in >> from >> to;
        graph[from].Children.push_back(to);
        graph[to].Parents.push_back(from);
    }

    return FindGraphComponents(graph);

}

void main() {

    size_t test_case_count;
    std::cin >> test_case_count;

    for (size_t test_case_i = 1; test_case_i <= test_case_count; ++test_case_i) {

        auto components = FindGraphComponents(std::cin);

       //Sort components by descending size and print them.
        std::sort(
            components.begin(),
            components.end(),
            [] (const Component& a, const Component& b) { return a.size() > b.size(); }
        );

        std::cout << "Case " << test_case_i <<  ": " << components.size() << " component (s) connected (s)" << std::endl;
        for (auto components_i = components.begin(); components_i != components.end(); ++components_i) {
            for (auto edge_i = components_i->begin(); edge_i != components_i->end(); ++edge_i)
                std::cout << *edge_i << ' ';
            std::cout << std::endl;
        }
        std::cout << std::endl;

    }

}

Викликати цю програму як ...

GraphComponents.exe < input.in > output.out

... де input.in містить дані у форматі, описаному у вашому запиті, і він дасть бажаний результат у output.out .