Number of Connected Components - Số thành phần liên thông đồ thị vô hướng

Cho n nút (0 đến n-1) và danh sách cạnh vô hướng. Đếm số thành phần liên thông.

Ví dụ: n=5, edges=[[0,1],[1,2],[3,4]] → 2 thành phần.

Giải thuật (DFS/BFS)

Xây dựng danh sách kề. Duyệt qua các nút, nếu chưa thăm thì DFS/BFS đánh dấu toàn bộ thành phần, tăng đếm.

Cài đặt C++

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

class Solution {
public:
    void dfs(int node, vector<int> graph[], vector<bool>& visited) {
        if (visited[node]) return;
        visited[node] = true;
        for (int v : graph[node])
            dfs(v, graph, visited);
    }

    int countComponents(int n, vector<vector<int>>& edges) {
        vector<bool> visited(n, false);
        if (!n) return 0;
        vector<int> graph[n];
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
            if (!visited[i]) {
                dfs(i, graph, visited);
                ret++;
            }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1},{1,2},{3,4}};
    cout << ob.countComponents(5, v);
    return 0;
}

Đầu vào

5, [[0,1],[1,2],[3,4]]

Đầu ra

2