323. Number of Connected Components in an Undirected Graph

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        var adj = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) adj[i] = new List<int>();
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        var visited = new HashSet<int>();
        int count = 0;
        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            while (stack.Count > 0) {
                var current = stack.Pop();
                if (visited.Add(current)) {
                    foreach (var neighbor in adj[current]) {
                        if (!visited.Contains(neighbor)) stack.Push(neighbor);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (visited.Add(i)) {
                Dfs(i);
                count++;
            }
        }
        return count;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountComponents(int n, int[][] edges) {
        var adj = new unordered_map<int, List<int>>();
        for (int i = 0; i < n; i++) adj[i] = new List<int>();
        foreach (var edge in edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        var visited = new HashSet<int>();
        int count = 0;
        void Dfs(int node) {
            var stack = new stack<int>();
            stack.push(node);
            while (stack.size() > 0) {
                var current = stack.pop();
                if (visited.push_back(current)) {
                    foreach (var neighbor in adj[current]) {
                        if (!visited.Contains(neighbor)) stack.push(neighbor);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (visited.push_back(i)) {
                Dfs(i);
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                count++;
            }
        }

        return count;
    }

    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited[current]) {
                visited[current] = true;
                for (int neighbor : adj.get(current)) {
                    if (!visited[neighbor]) stack.push(neighbor);
                }
            }
        }
    }
}

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;
}

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        from collections import defaultdict

        # Create adjacency list
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        visited = set()
        count = 0

        def dfs(node):
            stack = [node]
            while stack:
                current = stack.pop()
                if current not in visited:
                    visited.add(current)
                    stack.extend(adj[current])

        for i in range(n):
            if i not in visited:
                dfs(i)
                count += 1

        return count

package main

func countComponents(n int, edges [][]int) int {
    adj := make(map[int][]int)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }

    visited := make(map[int]bool)
    count := 0

    var dfs func(int)
    dfs = func(node int) {
        stack := []int{node}
        for len(stack) > 0 {
            current := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if !visited[current] {
                visited[current] = true
                for _, neighbor := range adj[current] {
                    if !visited[neighbor] {
                        stack = append(stack, neighbor)
                    }
                }
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i)
            count++
        }
    }

    return count
}

Explanation

Algorithm

Создание списка смежности

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

Инициализация посещенных узлов

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

Подсчет компонентов

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

😎