DFS: Как указать узлы подключенных компонентов в C ++

Question

Я делаю задачу на соревнованиях ACM, чтобы определить количество связанных компонентов, имеющих неориентированный граф G и вершины, принадлежащие каждому компоненту. Уже сделано с алгоритмом DFS, подсчитывающим количество связанных компонентов неориентированного графа (сложная часть проблемы), но я не могу придумать, что указывать узлы, принадлежащие каждому компоненту, или иметь запись узлов. 1001 *

Ввод: Первой строкой ввода будет целое число C, которое указывает количество тестовых случаев. Первая строка каждого теста содержит два целых числа N и E, где N представляет количество узлов в графе, а E - количество ребер в нем. Затем следуйте E строкам, каждая с 2 целыми числами I и J, где I и J представляют существование ребра между узлом I и узлом J (0 ≤ I, J

Выход: В первой строке каждого контрольного примера должна отображаться следующая строка «Случай G: P компонент (ы) подключен (ы)», где G представляет число контрольного примера (начиная с 1) и P количество компонентов, подключенных на графике. Затем X строк, каждая из которых содержит узлы, принадлежащие связанному компоненту (в порядке от наименьшего к наибольшему), разделенные пробелами. После каждого теста следует напечатать пустую строку. Вывод должен быть записан в "output.out."

Пример:

Введите:

2
6 9
0 1
0 2
1 2
5 4
3 1
2 4
2 5
3 4
3 5
8 7
0 1
2 1
2 0
3 4
4 5
5 3
7 6

Выход:

Case 1: 1 component (s) connected (s)
0 1 2 3 4 5

Case 2: 3 component (s) connected (s)
0 1 2
3 4 5
6 7

Вот мой код:

#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
vector<int> adjacency[10000];
bool visited[10000];

/// @param Standard algorithm DFS
void dfs(int u){
    visited[ u ] = true;
    for( int v = 0 ; v < adjacency[u].size(); ++v ){
        if( !visited[ adjacency[u][v] ] ){
            dfs( adjacency[u][v] );
        }
    }
}

    int main(int argc, char *argv []){
    #ifndef ONLINE_JUDGE
    #pragma warning(disable: 4996)
        freopen("input.in", "r", stdin);
            freopen("output.out", "w", stdout);
    #endif

         ///enumerate vertices from 1 to vertex
        int vertex, edges , originNode ,destinationNode, i, j,cont =1;
        ///number of test cases
        int testCases;
        int totalComponents;
        scanf ("%d", &testCases);

        for (i=0; i<testCases; i++){

        memset( visited , 0 , sizeof( visited ) );
        scanf("%d %d" , &vertex , &edges );
        for (j=0; j<edges; j++){
            scanf("%d %d" , &originNode ,&destinationNode );
            adjacency[ originNode ].push_back( destinationNode );
            adjacency[ destinationNode ].push_back( originNode );
        }
            totalComponents =0;
            for( int i = 0 ; i < vertex ; ++i ){    // Loop through all possible vertex
                if( !visited[ i ] ){          //if we have not visited any one component from that node
                    dfs( i );                  //we travel from node i the entire graph is formed
                    totalComponents++;                   //increased amount of components
                }
            }
            printf("Case %d: %d component (s) connected (s)\n" ,cont++, totalComponents);

            for (j=0;j<total;j++){
        /*here should indicate the vertices of each connected component*/
    }
        memset( adjacency , 0 , sizeof( adjacency ) );
        }
    return 0;
    }

У меня есть сомнения по поводу того, как переносить память узлов, принадлежащих каждому подключенному компоненту или структуре, для хранения, как я должен изменить свой код для этого ?, Я хотел бы услышать предложения, идеи или любую реализацию в псевдокод. Спасибо всем

Answer 1

Алгоритм примерно:

• Получить узел графа.
• Найти все узлы, прямо или косвенно связанные с ним (в обоих направлениях).
• Отметьте их как «пройденные» и поместите в новый компонент.
• Найдите следующий узел, который не пройден, и повторите процесс.

Результатом является набор «компонентных» структур данных (std::vector s в моей реализации), каждая из которых содержит набор исключительно взаимосвязанных узлов.

Вопросы:

• Нам нужно хранить график в структуре, которую можно эффективно обходить как «вниз» (от родителей к детям), так и «вверх» (от детей к родителям) и рекурсивно находить все связанные узлы (в обоих направлениях), помечая узлы как «пройденные», как мы идем. Поскольку узлы идентифицируются непрерывным диапазоном целых чисел, мы можем эффективно построить эту структуру, просто используя свойства произвольного доступа std::vector.
• Концепция ребер и узлов разделена, поэтому одиночный «пройденный» флаг может существовать на уровне узла, независимо от того, сколько других узлов подключено к нему (т.е. независимо от того, сколько родительские и дочерние ребра есть). Это позволяет нам эффективно сократить рекурсию для уже достигнутых узлов.

Вот рабочий код. Обратите внимание, что были использованы некоторые функции C ++ 11, но их должно быть легко заменить, если используется более старый компилятор. Обработка ошибок оставлена ​​читателю в качестве упражнения.

#include <iostream>
#include <vector>
#include <algorithm>

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

// Graph node.
struct Node {
    Node() : Traversed(false) {
    }
    std::vector<unsigned> Children;
    std::vector<unsigned> 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<Node>& 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<Component> FindGraphComponents(std::vector<Node>& graph) {

    std::vector<Component> 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<Component> 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<Node> 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.

Answer 2

решение гораздо проще, вы должны объявить два массива размером число вершин

int vertexNodes  [vertex] / / / array to store the nodes
int vertexComponents [vertex] / / / array to store the number of components

Затем, когда вы обращаетесь к DFS, каждая вершина сохраняется в массиве вершин и сохраняется при этом.компонент принадлежит

for( int i = 0 ; i < vertex ; ++i ) //iterate on all vertices
        {
                vertexNodes [i]=i;  //fill the array with the vertices of the graph
            if( !visited[ i ] )
            { ///If any node is visited DFS call
                    dfs(i);
                totalComponents++; ///increment number of components
            }
            vertexComponents [i]=totalComponents; ///is stored at each node component belongs to
        }

Наконец, он печатает все компоненты и создает флаг со значением первого компонента, который сравнивается с компонентом каждой вершины

printf("Case %d: %d component (s) connected (s)\n" ,cont++, totalComponents);
int flag = vertexComponents[0]; ///Create a flag with the value of the first component
            for (k=0; k <totalComponents; ++k) ///do a cycle length of the number of components
            {
                if (flag == vertexComponents [k] ) ///check if the vertex belongs to the first component
                {
                    printf ("%d ", vertexComponents[k]); ///print on the same line as belonging to the same component
                }else {
                    printf ("\n"); ///else  we make newline and update the flag to the next component
                    flag = vertexComponents[k];
                    printf ("%d ", vertexComponents[k]);///and print the vertices of the new connected component
                }
            }

Answer 3

Общий алгоритм проверки, подключены ли 2 узла:

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

Сначала ваши узлы будут в каждом наборе,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

По мере того, как алгоритм прогрессирует и объединяет множества, он относительно вдвое сокращает ввод.

В приведенном выше примере я искал, существует ли путь между o1 и o2. Я нашел этот путь только в конце после объединения всех ребер. Некоторые графики могут иметь отдельные компоненты (отключенные), что означает, что вы не сможете иметь один набор в конце. В таком случае вы можете использовать этот алгоритм для проверки связности и даже подсчитать количество компонентов в графе. Количество компонентов - это количество наборов, которое вы можете получить после завершения работы алгоритма.

Возможный график (для дерева выше):

o-o1-o-o-o2
  |    |
  o    o
       |
       o

Answer 4

Вы можете хранить компоненты следующим образом:

typedef vector<int> Component;
vector<Component> components;

и измените код:

void dfs(int u){
    components.back().push_back(u);
    visited[ u ] = true;
    for( int v = 0 ; v < adjacency[u].size(); ++v ){
        if( !visited[ adjacency[u][v] ] ){
            dfs( adjacency[u][v] );
        }
    }
}

for( int i = 0 ; i < vertex ; ++i ){    // Loop through all possible vertex
    if( !visited[ i ] ){          //if we have not visited any one component from that node
        components.push_back(Component());
        dfs( i );                  //we travel from node i the entire graph is formed
    }
}

теперь totalComponents is components.size ():

printf("Case %d: %d component (s) connected (s)\n" ,cont++, components.size());

        for (j=0;j<components.size();j++){
           Component& component = components[j];
           std::sort(component.begin(), component.end());
           for(int k=0; k<component.size(); k++) {
             printf("%d ", component[k]);
           }
           printf("\n");
        }
        components.clear();

Обратите внимание, что код не проверен. Включите <algorithm>, чтобы получить функцию сортировки.