天梯赛-L2-038 病毒溯源

题目详情：

思路:

这个题目是一个遍历的题目，不管是深度优先遍历，还是广度优先遍历，都是可以写出来的。我采用vector容器作为邻接表存放数据，那么需要解决几个问题？
1、如何找到根节点，如何解决最小序列问题
答：找到根节点很简单，我们每次输入数据的时候，把所有出现的节点都标记为1，而没有被标记为1的节点肯定就是我们要找的根节点了。解决最小序列：只需要我们每次都输入完一组数据后直接用sort排序就可以了。

2、在遍历的同时，不仅需要我们同时记住层数，还需要把最深的路径记录下来。
答：这个问题容易解决，我们用vector容器v[maxn]容器存放数据，在DFS过程中，如果我们找到更深的，那么我们就把当前的容器的v[i]赋给另外一个vector容器temp。让temp一直存放最深的数据。而temp的大小，就是我们要求的层数了。一举两得！

3、同时本题还要进行回溯。为什么呢？
答：首先，我们要什么是回溯？回溯非常简单：当你在遍历二叉树时，B和C是A的节点，你遍历B之后，需要回到A，接着遍历C，B回到A的这个过程就回溯。回溯就是要求我们把所有情况都枚举出来，在这之中找到我们要的答案。像图的深度优先遍历以及二叉树找节点的距离就不需要回溯，因为本身就是要遍历所有节点，而不是找到所有情况。
那么什么情况下需要回溯呢？
需要我们不断尝试，把所有情况都列举出来，才可以找到答案的时候。就比如本题，为什么要回溯？DFS是将所有节点都遍历一遍，如果不回溯，那么，最后的结果就会是所有的节点全部存放在temp中。
所以，必须要回溯，每次判断完节点深度的时候，都需要返回父节点去判断另外节点的深度。如果这里不是很理解，看一下代码就可以了。

详细代码:

#includeusing namespace std;int n;const int maxn=10005;vector<int>v[maxn];//邻接表存放所有数据vector<int>temp, ans;//temp存放符合条件的序列，//ans存放根节点：然后将所有孩子节点逐个放入，边回溯边遍历int root[maxn];//找根节点void Dfs(int index)//孩子下标为index{if(ans.size()>temp.size())//找到更深的，更新temp    {temp.clear();//每次更新temp，需要先把temp清空，防止其他的情况temp=ans;}for(int i=0; i<v[index].size(); i++)//标号为index的孩子节点    {ans.push_back(v[index][i]);//先将孩子节点入pDfs(v[index][i]);//深搜孩子节点ans.pop_back(); //回溯//这里可以把回溯去掉，然后你看看是什么情况,将会是所有的节点都会放入temp中}}int main(){cin>>n;for(int i=0; i<n; i++)    {int k;cin>>k;while(k--)//当k等于0 时，就不用考虑 {int x;cin>>x;v[i].push_back(x);root[x]=1;//将所有的孩子节点的root都设为1，这样只需要找到不是1的节点，那个节点就是根节点了}if(v[i].size()) {sort(v[i].begin(),v[i].end());//每次放完孩子都需要排序，以求得最小的编号//这是排序是将最小节点的孩子，放在了父节点的左边，即开始遍历的时候，肯定是从左边先遍历，然后这个时候如果两个序列一样长，那么序列小的肯定先被放入temp中，序列大的就不会被放进去。}}for(int i=0; i<n; i++)    {if(!root[i])//找到根节点进行深搜 {ans.push_back(i);Dfs(i);//从根节点开始搜索，每次更新ansbreak;}}cout<<temp.size()<<endl;for(int i=0; i<temp.size(); i++)    {if(!i)      cout<<temp[i];else     cout<<" "<<temp[i];}}

知识总结:

1、这里面用到的知识点：回溯，DFS，vector作为邻接表。DFS在天梯赛题目中还是非常多的一定要多多练习啊。DFS说白了，就是递归，好好学习，天天向上！
最后附上用vector作为邻接表存图的代码，不会这么用的小伙伴可以看一下：

#includeusing namespace std;const int maxn = 10005;vector<int> E[maxn];int n,m;//结点数，边数 void createVec()//用vector存储无向图 {int u,v;cin>>n>>m;for(int i = 0; i < m; i++)//m为边数 {cin>>u>>v;//一条边的两个结点编号 E[u].push_back(v);E[v].push_back(u);}}void printg()//输出邻接表 {cout<<"图的邻接表为："<<endl; for(int u = 0; u < n; u++){cout<<u<<"-->";for(int i = 0; i < E[u].size(); i++)//访问u的所有邻接点 {int v = E[u][i];cout<<"["<<v<<"]\t"; }cout<<endl;}}int main(){createVec();printg();return 0;}

清水丽人化妆品