模版题怎么人这么少 \think

Solution

使用 邻接表 + DFS 进行遍历即可。

怎么把邻接矩阵转换成邻接表呢？

邻接矩阵的本质就是存储 i 和 j 是否相连，
所以我们在输入时遇到 1 就 g[i].push_back(j) 就可以了.

需要注意的点：

• 为了防止递归超限，需要使用一个 vis 数组存储是否访问
• 答案存储需要用 vector
• 注意输出格式

AC Code

#include <iostream>
#include <vector>
using namespace std;
const int N=22;
vector<int> g[N]; 
vector<int> ans;
int n;
bool vis[N];
void dfs(int u){
    ans.push_back(u); // 添加答案
    vis[u] = 1; // 标记
    for(int v:g[u]){
        if(vis[v]) continue; // 如果访问过就不再递归
        dfs(v);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            // 将邻接矩阵转为邻接表
            bool b; cin>>b;
            if(b) g[i].push_back(j);
        }
    }
    dfs(1); // 要求从顶点开始
    for(auto x:ans){
        cout<<x;
        // 这里注意输出格式，ans.back() 表示 ans 的最后一个元素
        if(x != ans.back()) cout<<'-';
    }
    return 0;
}