Число компонент связности: считать DFS-ом или через СНМ — и как быстрее на потоке рёбер?

Статический случай — DFS/BFS. Число запусков обхода из непосещённых вершин = число компонент:

int countComponents(int n, vector<int> g[]) {
    vector<bool> used(n, false); int comp = 0;
    for (int s = 0; s < n; s++) if (!used[s]) {
        comp++;
        // BFS/DFS, помечая всю компоненту used
        queue<int> q; q.push(s); used[s] = true;
        while (!q.empty()) { int v=q.front(); q.pop();
            for (int u: g[v]) if(!used[u]){used[u]=true; q.push(u);} }
    }
    return comp;
}

O(V+E).

Онлайн-добавление рёбер — СНМ. Стартуем с comp = n (каждая вершина — своя компонента). При добавлении ребра (a,b): если unite(a,b) реально слил две разные компоненты — comp--. Так число компонент поддерживается инкрементально за O(α) на ребро:

DSU d(n); int comp = n;
// на каждое новое ребро:
if (d.unite(a, b)) comp--;   // ответ comp всегда актуален

Итого добавить m рёбер и отвечать после каждого — O(m·α(V)), практически линейно. Это куда лучше, чем перезапускать DFS (O(m·(V+E))).

Важно: СНМ умеет только объединять. Если рёбра ещё и удаляются (онлайн disconnect), обычный СНМ не поможет — там нужны оффлайн-приёмы (обработка запросов в обратном порядке, превращающая удаление в добавление) или сложные структуры (link-cut tree / дерево разрезов).