
中国科学技术大学计算机学院机试——06-t5
众所周知,图有两种主要的存储方式,分别为邻接矩阵和邻接表,二者的时间复杂度和空间复杂度在实现不同算法时各不相同。我们在考试中更推荐邻接矩阵,无他,遍历方式相对于邻接表简单太多了。在后面所有和图相关的题目,我们都将基于邻接矩阵存储,如果对邻接表有兴趣,可以自行咨询deepseek,这里就不再赘述了。题目难度中等偏上,需要一定的逻辑构建能力,初见可以反复思考每一步是怎么得到的,不过仍然存在可以套用模板
题目要求
给定一无向图的矩阵存储,求其最大连通分量。图的信息存储在文件graph.in中,文件的第一行给无向图的顶点数量n和边数k,顶点序号从0到n-1,接下来分别给出k条边的两个顶点号。输出无向图中的最大连通分量的所有顶点号,输出到文件graph.out中。
输入示例:
10 6
0 1
0 2
4 5
4 6
5 7
8 9
输出示例:
4 5 7 6
前置知识点
深度优先遍历(DFS)
学习过408之后应该还有印象,图的遍历分为广度优先遍历BFS和深度优先遍历DFS,其中BFS需要借助队列(queue),DFS需要借助栈(stack)或递归,该题目就属于DFS的模板题,此处给出DFS的模板:
void dfs(int node,vector<int> nums,vector<bool>& used){
used[node]=true;//表明该结点被访问
operate();//对该节点进行操作,具体的需要看题目
for(int i=0;i<nums.size();i++){
if(!used[i]){//如果下一个结点未被访问,则进行dfs
dfs(i,nums,used);
}
}
}
图的存储方式
众所周知,图有两种主要的存储方式,分别为邻接矩阵和邻接表,二者的时间复杂度和空间复杂度在实现不同算法时各不相同。我们在考试中更推荐邻接矩阵,无他,遍历方式相对于邻接表简单太多了。在后面所有和图相关的题目,我们都将基于邻接矩阵存储,如果对邻接表有兴趣,可以自行咨询deepseek,这里就不再赘述了。
题目分析
首先根据测试用例画出图的形状:
通过肉眼观察法可得,最大连通分量为4 5 6 7。
这个题目我们可以分为以下几步:
- 将图以邻接矩阵的方式导入到程序中
- 求最大连通分量
如果要求得最大连通分量,我们可以对每一个点进行DFS,每个点的不同情况如下:
- 情况一:该点未被遍历过:此时从该点开始dfs,记录后序该连通分量中的点,并和当前记录的最大连通分量进行比较,更新最大连通分量;
- 情况二:该点已被遍历过:此时直接跳过即可。
代码实现
阅读顺序main()->findMax()->dfs()最佳
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
void dfs(int node,vector<vector<int>> adj,vector<bool>& used,vector<int>& curr){//dfs
used[node]=true;//表明该结点被遍历过
curr.push_back(node);//将该结点加入到当前连通分量中
for(int i=0;i<adj.size();i++){
if(adj[node][i]&&!used[i]){//如果i与node相连且i未被遍历
dfs(i,adj,used,curr);
}
}
}
void findMax(vector<vector<int>> adj,int n,ofstream& ofs){//核心功能
vector<bool> used(n,false);//通过used数组表明结点是否被访问过
vector<int> res;//存储最大连通分量
for(int i=0;i<n;i++){//对每个结点进行遍历
if(!used[i]){//如果该结点未遍历过(该节点可能在之前的结点中被dfs访问)
vector<int> curr;//存储当前连通分量
dfs(i,adj,used,curr);//dfs
if(curr.size()>res.size())//更新最大连通分量
res=curr;
}
}
for(int x:res){
ofs<<x<<" ";//输出到文件中,用法和cout相同
}
}
int main(){
ifstream ifs("./graph.in");//建立文件链接
ofstream ofs("./graph.out");
int n,k;
ifs>>n>>k;//根据题目要求先输入n和k
vector<vector<int>> adj(n,vector<int>(n,0));//构造一个n*n的邻接矩阵,初始值为0表明不连通(也可用-1,INT_MAX等)
for(int i=0;i<k;i++){
int l,r;
ifs>>l>>r;//依次导入边的两端结点
adj[l][r]=1;//在邻接矩阵中添加边
adj[r][l]=1;//注意此题为无向图,如果为有向图则不需要添加这条边
}
findMax(adj,n,ofs);
return 0;
}
题目总评
难度指数:⭐⭐⭐⭐
题目难度中等偏上,需要一定的逻辑构建能力,初见可以反复思考每一步是怎么得到的,不过仍然存在可以套用模板的部分,故给到4⭐。
更多推荐
所有评论(0)