Подсчет компонент связности
Урок 13 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Связная компонента — это максимальное множество вершин, в котором между любой парой вершин существует путь. Граф без ребер имеет столько же компонент, сколько и вершин; полностью связный граф имеет ровно одну компоненту.
Чтобы их подсчитать, обойдите все вершины. Каждый раз, когда вы находите вершину, которая еще не была посещена, это новая компонента: увеличьте счетчик, а затем выполните BFS или DFS из этой вершины, чтобы пометить все достижимые вершины как посещенные. Продолжайте со следующей непосещенной вершиной.
В этой задаче вам даны И список вершин, И ребра, потому что изолированные вершины (без ребер) все равно считаются отдельными компонентами, и нам нужно знать об их существовании.
Задание
ЛегкоНапишите функцию countConnectedComponents, которая принимает двумерный массив целых чисел adjacency и массив целых чисел vertices, и возвращает количество компонент связности в графе.
Постройте граф: сначала вызовите addVertex для каждого ключа в vertices (чтобы присутствовали изолированные вершины), затем addEdge для каждой пары в adjacency. Затем обойдите все вершины: каждая непосещенная вершина начинает новую компоненту (увеличьте счетчик), после чего выполните DFS/BFS из нее, чтобы пометить всю ее компоненту как посещенную.
Вы должны использовать класс Graph (предоставленный в graph) — не используйте встроенные средства языка (словари, множества) для моделирования смежности. Вспомогательные данные для алгоритма (множества посещенных вершин, стеки) могут использовать типы стандартной библиотеки.
Попробуйте сами
#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;
}