邻接矩阵DFS怎么找连通分量个数

邻接矩阵DFS找连通分量的个数可以采用以下步骤：

1. 初始化一个标记数组，记录每个顶点是否被访问过，初始值为false。

2. 对于每个未被访问的顶点，进行DFS遍历，并将其所在的连通分量中的所有顶点标记为已访问。

3. 每次遍历一个未被访问的顶点，就将连通分量的个数加1。

4. 最终得到的连通分量的个数即为答案。

以下是示例代码：

//邻接矩阵DFS找连通分量的个数
#include <iostream>
using namespace std;

const int MAXN = 100; //最大顶点数
int G[MAXN][MAXN]; //邻接矩阵存储图
bool vis[MAXN]; //标记数组，记录每个顶点是否被访问过

void dfs(int u, int n) //DFS遍历
{
    vis[u] = true; //标记该顶点已被访问
    for(int v=0; v<n; v++) //遍历与该顶点相连的所有顶点
    {
        if(G[u][v] && !vis[v]) //如果该顶点与相邻顶点之间有边，并且相邻顶点未被访问过
        {
            dfs(v, n); //继续遍历与相邻顶点相连的所有顶点
        }
    }
}

int connectedComponents(int n) //求连通分量的个数
{
    int cnt = 0; //记录连通分量的个数
    for(int i=0; i<n; i++) //对于每个未被访问的顶点
    {
        if(!vis[i]) //如果该顶点未被访问过
        {
            cnt++; //连通分量个数加1
            dfs(i, n); //从该顶点开始进行DFS遍历
        }
    }
    return cnt; //返回连通分量的个数
}

int main()
{
    int n, m; //n为顶点数，m为边数
    cin >> n >> m;
    for(int i=0; i<m; i++) //读入边
    {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1; //无向图存储方式
    }
    cout << connectedComponents(n) << endl; //输出连通分量的个数
    return 0;
}

在该代码中，我们首先读入了图的顶点数和边数，然后使用邻接矩阵存储图，并且对于每个未被访问的顶点，进行DFS遍历，并将其所在的连通分量中的所有顶点标记为已访问，最终得到的连通分量的个数即为答案。