病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。
现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。
在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题——即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。
输入格式：
输入在第一行中给出一个正整数N，即病毒种类的总数。于是我们将所有病毒从0到N−1进行编号。
随后N行，每行按以下格式描述一种病毒的变异情况：
k 变异株1 …… 变异株k
其中k是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第i行对应编号为i的病毒。题目保证病毒源头有且仅有一个。
输出格式：
首先输出从源头开始最长变异链的长度。
在第二行中输出从源头开始最长的一条变异链，编号间以1个空格分隔，行首尾不得有多余空格。如果最长链不唯则输出最小序列。
注：我们称序列{a1,⋯,an}比序列{b1,⋯,bn}“小”，如果存在1≤k≤n满足ai=bi对所有i 输出样例40491 思路：将数据存储在二维数组中，然后利用深度优先搜索和回溯处理数据。 文章为作者独立观点，不代表股票交易接口观点#include<bits/stdc++.h>
using namespace std;
vector<int>q;
vector<vector<int>>num;//存放输入数据
vector<vector<int>>q1;//存放最后结果
int res;
//当数组大小相等时，输出较小的一组
bool cmp(vector<int> a, vector<int> b) {
if (a.size() == b.size()) {
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[i]) {
continue;
}
else {
return a[i] < b[i];
}
}
}
return a.size() > b.size();
}
//dfs+回溯将每组数据存入q1中
void dfs(int i) {
if (num[i].size() == 0) {
q1.emplace_back(q);
return;
}
for (int j = 0; j < num[i].size(); j++) {
q.emplace_back(num[i][j]);
dfs(num[i][j]);
q.pop_back();
}
}
int main() {
int n;
cin >> n;
vector<int>flag(n, 0);//为找根节点设置判断数组
//处理输入的各组数据，将每个节点的子节点存入数组中
for (int i = 0; i < n; i++) {
int a;
cin >> a;
vector<int>ans;
for (int j = 1; j <= a; j++) {
int b;
cin >> b;
flag[b] = 1;
ans.emplace_back(b);
}
if (ans.size()) {
sort(ans.begin(), ans.end());
}
num.emplace_back(ans);
}
//找根节点
for (int i = 0; i < n; i++) {
if (flag[i] == 0) {
q.emplace_back(i);
res = i;
break;
}
}
dfs(res);
//输出结果
sort(q1.begin(), q1.end(), cmp);
cout << q1[0].size() << endl;
for (int i = 0; i < q1[0].size(); i++) {
if (i == 0)
cout << q1[0][i];
else
cout << " " << q1[0][i];
}
return 0;
}
相关文章
股民评论