试设计一个算法Mark标记一个无向图G的各个连通分量，即第i个连通分量标记为i。 （1）用自然语言描述算法思想； （2）用类C或C++语言描述算法的实现； （3）分析算法的时间复杂度

（1）算法思想：从图中的任意一个未被标记的节点开始，进行深度优先搜索，将搜索到的所有节点都标记为同一个连通分量，直到搜索完所有未被标记的节点，即可得到该图的所有连通分量。

（2）C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

vector<int> G[MAXN]; // 存储图G
int vis[MAXN]; // 标记节点是否被访问过
int cnt = 0; // 记录当前连通分量编号

void dfs(int u) { // 深度优先搜索
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            dfs(v);
        }
    }
}

void mark_components(int n) { // 标记所有连通分量
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt++;
            dfs(i);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图G的节点数n和边数m
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        G[u].push_back(v);
        G[v].push_back(u); // 无向图需要双向存储
    }
    mark_components(n); // 标记所有连通分量
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << " is in component " << vis[i] << endl;
    }
    return 0;
}

（3）算法的时间复杂度为O(n + m)，其中n为节点数，m为边数。因为每个节点最多只会被访问一次，每条边也最多只会被遍历一次。所以时间复杂度为O(n + m)。