题目要求

给定一无向图的矩阵存储,求其最大连通分量。图的信息存储在文件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。
这个题目我们可以分为以下几步:

  1. 将图以邻接矩阵的方式导入到程序中
  2. 求最大连通分量

如果要求得最大连通分量,我们可以对每一个点进行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⭐。

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐