数连通分量

图能分成几块互不相连的部分，每一块叫一个连通分量。数法和"数岛屿/数陆地"一模一样：从头扫每个点，遇到还没访问过的点，说明发现了新的一块，计数加一，然后从它出发把整块（所有能到的点）都走遍标记掉；接着扫下一个没访问的点。

int cnt = 0;
for (int i = 1; i <= n; i++)
    if (!vis[i]) {            // 一个新的连通块
        cnt++;
        dfs(i);              // 把这一块全标记
    }
cout << cnt;

复杂度 $O(n+m)$：外层扫每个点，内层每条边总共只走一次。理解要点：外层循环负责"发现新块"，一次 DFS/BFS 负责"吃掉一整块"。所以如果一次搜索就把所有点走遍了，$cnt$ 最后是 $1$，说明整张图连通、本来就是一块。坑：外层一定要遍历所有点，不能只从 $1$ 号点搜一次——那只能覆盖 $1$ 号所在的那一块，别的块会漏掉。此外用并查集也能数连通分量，值得了解。