DFS:如何在C++中指示连接组件的节点

Question

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

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

输出:在每个测试用例的第一行中必须显示以下字符串"Case G:P(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

解决方案更容易，您必须声明两个大小为顶点数的数组

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
                }
            }