题目描述
给定一棵由 \(n\) 个顶点组成的有根树。顶点由 \(1\) 到 \(n\) 编号。任何顶点都可以是树的根。
请在树上找出这样一组路径：
- 每个顶点恰好属于一条路径，每条路径可以包含一个或多个顶点；
- 在每条路径中，每个节点的下一个节点是当前节点的子节点（即路径总是向下 —— 从父节点到子节点）；
- 路径的数量最少。
思路
很明显，任何一棵树，如果我们按照其深度优先遍历的顺序分段（每次向后退时分一段），那么得到的一定是最小的路径数量。
为什么呢？想象一下，假如我们到达了一个节点，他有三个子节点，无论选哪个，路径都最少会分出三个叉来
所以，这道题就成了一道深搜
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int n,cnt,root;
int p[Maxn];
vector<int>node[Maxn];
vector<int>ans[Maxn];
void find(int now)
{
ans[cnt].push_back(now);
if(node[now].size()==0)
{
cnt++;
return ;
}
for(int i=0;i<node[now].size();i++) find(node[now][i]);
}
void run()
{
cin>>n;cnt=0;
vector<int>t;
for(int i=0;i<=n+1;i++) ans[i]=t,node[i]=t;
for(int i=1;i<=n;i++)
{
cin>>p[i];
if(p[i]==i) root=i;
else
{
node[p[i]].push_back(i);
}
}
find(root);
cout<<cnt<<endl;
for(int i=0;i<cnt;i++)
{
cout<<ans[i].size()<<endl;
for(int j=0;j<ans[i].size();j++)
{
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) run();
}