Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

👨‍💻 Алгоритм:

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

function countComponents(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    edges.forEach(([u, v]) => {
        adj[u].push(v);
        adj[v].push(u);
    });

    const visited = new Set();
    let count = 0;

    const dfs = (node) => {
        const stack = [node];
        while (stack.length > 0) {
            const current = stack.pop();
            if (!visited.has(current)) {
                visited.add(current);
                adj[current].forEach(neighbor => {
                    if (!visited.has(neighbor)) stack.push(neighbor);
                });
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }

    return count;
}

Ставь 👍 и забирай 📚 Базу знаний