JakeLin

用户名：jake546

访问量：43192

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）
浏览：536

JakeLin-1495题-传染病控制-题解(C++代码)-DFS+BFS
浏览：1047

JakeLin-1506题-卡勒沃夫之弱水路三千(提高型)-题解(C++代码)-拓扑排序（详细解析+图解）
浏览：559

你可能喜欢

连通图 -题解(C/C++) DFS-深度优先遍历

　　作者: JakeLin　　　　发表时间：2020-01-10 20:21:53 浏览：1195　|　评论：0　

原题链接：连通图

这道题本质还是一道图的遍历题，跟我一起**三步走**：
- #####第一步：构建地图
 - **确定一个存储图的数据结构：**本题我选用**邻接表**，map是一个二维数组，map【i】表示i的邻接节点**们**
 - **输入数据构建图：**根据题意可知，一组输入【i j】指的是i与j之间有联系，并没有方向，所以这应该是个无向图，我们确定map【i】=j的同时，也要确定map【j】=i

------------

- #####第二步：遍历地图
本题我们选用bfs最为简单，其原理是：遍历访问当前节点的每一个邻居节点，并将其标志为（vis【#】）已访问（后序不用再访问），直到所有节点访问结束

------------

- ##### 第三步：判断连通性
   ***关键：**若是连通图，我们应该知道从一个节点开始访问可以访问到任意一个节点，所以我们可以统计遍历图时访问的节点量，如果少于节点总数，那么说明它不是连通图了，它还有另一部分没法访问到

------------

> 解释就到这里了，是不是还挺清晰的呢，接下来我们看看代码：
   
   
    #include<stdio.h>
    #include<cmath>
    #include<iostream>
    #include<vector>
    using namespace std;
    const int maxn = 1000 + 10;
    vector<int> map[maxn];   //map[i]保存i节点的邻居节点   
    int vis[maxn];    
    void dfs(int r,int &ans){
    	vis[r]=1;
    	//cout<<r<<" ";   //将这个注释打开可以看看遍历结果，加深一下bfs的了解
    	ans++;
    	for(int i=0;i<map[r].size();i++){
    		if(vis[map[r][i]]==0){
    			dfs(map[r][i],ans);
    		}
    	}
    } 
    int main(){
    	int n,m,ans;
    	while(cin>>n>>m){
    		if(n==0 && m==0) break;
    		ans=0;
    		memset(vis,0,sizeof(vis));
    		memset(map,0,sizeof(map));
    		int a,b;
    		for(int i=0;i<m;i++){  //构建地图  (邻接表儿)
    			cin>>a>>b;
    			map[a].push_back(b);
    			map[b].push_back(a);
    		}
    		dfs(a,ans);
    		if(ans==n){
    			cout<<"YES"<<endl;
    		}else{
    			cout<<"NO"<<endl;
    		}
    	}
        return 0;
    }
    
###### 如果对你有帮助麻烦加个评分哦(⊙o⊙)

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

连通图 -题解(C/C++) DFS-深度优先遍历

评论区

精彩推荐

大神老白（C语言代码）

奖学金（C++代码）

C语言训练-计算1977！* （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

wu-理财计划（C++代码）

WU-链表数据求和操作（C++代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

程序员的表白（C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

连通图 -题解(C/C++) DFS-深度优先遍历

评论区

精彩推荐

大神老白 （C语言代码）

奖学金 （C++代码）

C语言训练-计算1977！* （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

wu-理财计划 （C++代码）

WU-链表数据求和操作 （C++代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

程序员的表白 （C语言代码）

　　评论区

大神老白（C语言代码）

奖学金（C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

wu-理财计划（C++代码）

WU-链表数据求和操作（C++代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

程序员的表白（C语言代码）