Policz spójne składowe
Lekcja 13 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Składowa spójna to maksymalny zbiór wierzchołków, w którym każda para ma między sobą ścieżkę. Graf bez krawędzi ma tyle składowych, ile wierzchołków; graf w pełni spójny ma dokładnie jedną składową.
Aby je policzyć, przejdź przez wszystkie wierzchołki. Gdy znajdziesz taki, który nie został jeszcze odwiedzony, oznacza to nową składową: zwiększ licznik, a następnie wykonaj BFS lub DFS od tego wierzchołka, aby oznaczyć jako odwiedzone wszystkie osiągalne wierzchołki. Kontynuuj od następnego nieodwiedzonego wierzchołka.
To wyzwanie podaje zarówno listę wierzchołków, jak i krawędzie, ponieważ izolowane wierzchołki (bez krawędzi) nadal liczą się jako osobne składowe i musimy wiedzieć, że istnieją.
Wyzwanie
ŁatwyNapisz funkcję countConnectedComponents, która otrzymuje dwuwymiarową tablicę int adjacency oraz tablicę int vertices i zwraca liczbę składowych spójności grafu.
Zbuduj graf: najpierw wywołaj addVertex dla każdego klucza w vertices (aby uwzględnić także wierzchołki izolowane), a następnie wywołaj addEdge dla każdej pary w adjacency. Potem przejdź przez wszystkie wierzchołki: każdy nieodwiedzony rozpoczyna nową składową (zwiększ licznik), a następnie wykonaj z niego DFS/BFS, aby oznaczyć całą jego składową jako odwiedzoną.
Musisz użyć klasy Graph (udostępnionej w graph) — nie używaj wbudowanych mechanizmów języka (map, zbiorów) do modelowania sąsiedztwa. Pomocnicze dane algorytmu (zbiory odwiedzonych wierzchołków, stosy) mogą korzystać z typów biblioteki standardowej.
Spróbuj swoich sił
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}
Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9
Poćwicz samodzielnie: Kompilator C online