c++ - DFS : How to indicate the nodes of the connected components in C++

Question

我正在做一个 ACM 竞赛的问题，以确定具有无向图 G 和属于每个组件的顶点的连通组件的数量。已经完成了 DFS 算法，计算无向图的连接组件的数量(问题的难点)，但我想不出任何东西来指示属于每个组件的节点或有节点的记录。

输入: 第一行输入一个整数C，表示测试用例的个数。每个测试用例的第一行包含两个整数 N 和 E，其中 N 表示图中的节点数，E 表示图中的边数。然后是E行，每行有2个整数I和J，其中I和J表示节点I和节点J之间存在一条边(0≤I，J

输出:在每个测试用例的第一行必须显示以下字符串“Case G: P component(s) connected(s)” ，其中 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)，每个结构都包含一组专门互连的节点。

注意事项:

• 我们需要将图存储在一个结构中，该结构可以有效地“向下”(从 parent 到 child )和“向上”(从 child 到 parent )遍历并递归地找到所有连接的节点(在两个方向上)，在我们进行时将节点标记为“已遍历”。由于节点由连续的整数范围标识，因此我们只需使用随机访问属性 std::vector 即可高效地构建此结构。
• 边和节点的概念是分开的，所以一个单个“遍历”标志可以存在于节点级别，无论有多少其他节点连接到它(即无论如何有许多 parent 和 child 的边缘)。这使我们能够有效地减少已到达节点的递归。

这是工作代码。请注意，使用了一些 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 中产生所需的结果。