本文共 1154 字，大约阅读时间需要 3 分钟。

序：

dfs求连通分量

题目概述：

给出各边的连接关系，一开始是连通图。求去掉某个点之后的连通分量个数。

分析：

1.用邻接矩阵+visit存储 2.对每个点进行一次dfs，将所有直接或间接与它相邻的点都置为true，一条条扩散出去 3.这里的dfs思路是先设置当前点visit为true再遍历其dfs遍历其邻居。

#include
   
    using namespace std;int edge[1010][1010];bool visit[1010];int n, m, k;void dfs(int start){
       visit[start] = true;    for(int i = 1; i <= n; i++)    {
           if(edge[start][i] == 1 && visit[i] == false)            dfs(i);    }}int main(){
       cin >> n >> m >> k;    int a, b, c;    for(int i = 0; i < m; i++)    {
           cin >> a >> b;        edge[a][b] = edge[b][a] = 1;    }        for(int i = 0; i < k; i++)    {
           int cnt = 0;        fill(visit, visit + 1010, false);//每次都要初始化,注意这里最好全数组统一        cin >> c;        visit[c] = true;//挖掉这个点        for(int j = 1; j <= n; j++)        {
               if(visit[j] == false)            {
                   dfs(j);                cnt++;            }        }        printf("%d\n", cnt - 1);    }    return 0;}
   

总结：

1.fill那里最好把整个visit全部填满，即用1010，不要用n。用n会导致答案错误。由于是从1开始遍历的，所以一般要去到n+1,但经过实验发现最少也要n+3以上才行。因此，最好在写代码时避开边界，把数组开大一丢丢，再整体进行操作。 2.这是经典的图的dfs，思路就是先改visit，后面再dfs遍历所有邻居。外层引用时全部节点遍历一遍，同时要求遍历节点的visit为false。

转载地址：https://bridge-killer.blog.csdn.net/article/details/115440501 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！