無向グラフGと各コンポーネントに属する頂点を持つ連結成分の数を決定するためにACM競合の問題を作成しています。すでにDFSアルゴリズムを使用して、無向グラフの連結成分の数を数えていますが（問題の難しい部分）、各成分に属するノードを示したり、ノードの記録を持ったりすることは考えられません。
入力：入力の最初の行は、テストケースの数を示す整数Cになります。各テストケースの最初の行には、2つの整数NとEが含まれています。ここで、Nはグラフ内のノードの数を表し、Eはグラフ内のエッジの数を表します。次に、それぞれ2つの整数IとJを持つE線をたどります。ここで、IとJは、ノードIとノードJの間にエッジが存在することを表します（0≤I、J
出力：各テストケースの最初の行に、次の文字列「ケースG：接続されたPコンポーネント（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;
}
接続された各コンポーネントまたは構造に属するノードのメモリをどのように運ぶか、保存に使用する必要があるか、これを行うためにコードをどのように変更する必要があるかについて疑問があります。提案、アイデア、または擬似コードでの実装を聞きたいです。ありがとうございます