Я роблю проблему змагань ACM для визначення кількості підключених компонентів, які мають неорієнтований граф G і вершини, що належать кожному компоненту. Уже виконано з алгоритмом DFS, підрахунок кількості підключених компонентів неорієнтованого графа (важка частина проблеми), але я не можу нічого придумати, щоб вказати вузли, що належать кожному компоненту або мати запис вузлів.
Вхідні дані: The first line of input will an integer C, which indicates the number of test cases. The first line of each test case contains two integers N and E, where N represents the number of nodes in the graph and E the number of edges in it. Then follow E lines, each with 2 integers I and J, where I and J represent the existence of an edge between node I and node J (0 ≤ I, J
Вихід: In the first line of each test case must display the following string "Case G: P component (s) connected (s)", where G represents the number of test case (starting at 1) and P the number of components connected in the graph. Then X lines, each containing the nodes belonging to a connected component (in order from smallest to largest) separated by spaces.
After each test case should print a blank line. The output should be written in the "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
#include
#include
#include
using namespace std;
vector 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
У мене є сумніви про те, як носити пам'ять вузлів, що належать кожному з'єднаному компоненті або структурі, повинні бути використані для зберігання, як я повинен змінити свій код, щоб зробити це? Дякую всім