【xdoj-离散线上练习】T251（C++）
解题反思：
- 开始敲代码前想清楚整个思路比什么都重要嘤嘤嘤！
- 看到输入m, n和矩阵，注意不能想当然地认为就是高m，宽n的矩阵，细看含义
- 比如本题给出了树的邻接矩阵，就是n*n的，代码实现中没有用到m这个条件
- 不熟语法
-
vector<vector<int>>tree(m, vector<int>(n, 0)); //定义二维m*n数组tree，并将每个元素初始化为0；
题目见下
题目：任意构造一棵树，输出以指定的某一结点为根节点的子树。
问题描述
任意构造一棵树，输出以指定的某一结点为根节点的子树。下面给出一个样例示意图，输入样例的邻接矩阵，输出分别以a，c，e结点为根节点的子树。
输入格式
第一行输入图的顶点数n和边数m，第二行开始输入树的邻接矩阵（结点名称默认为1,2,3,...,n）。第n+2行输入1,2,3,...,n中选定的某一结点A。
输出格式
选择某一结A点为树根后，出现数字以及（数字1，数字2）的形式，
数字表示点，（数字1，数字2）表示以1、2为顶点的边，将各个顶点依照（）里的关系组合起来，即以输入字母为顶点的子树。
样例输入
21 20
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
样例输出
3 (3,7)7 (3,8)8 (8,15)15 (8,16)16
题目分析&代码实现
其实就是一个树的深度优先搜索的变形，本代码用lambda表达式实现递归函数。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin>>n>>m;
vector<vector<int>>tree(n+1, vector<int>(n+1));//注意从1开始！
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cin>>tree[i][j];
}
}
int root; cin>>root;
auto dfs = [&](auto& dfs, int cur) -> void
{
for(int i=1; i<=n; i++)
{
if(tree[cur][i] == 1)
{
cout<<"("<<cur<<","<<i<<")"<<i<<" ";
dfs(dfs, i);
}
}
return;
};
cout<<root<<" ";
dfs(dfs, root);
return 0;
}