题目要求

给定一无向图的矩阵存储，求其最大连通分量。图的信息存储在文件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⭐。