病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株,而这些变异的病毒又可能被诱发突变产生第二代变异,如此继续不断变化。
现给定一些病毒之间的变异关系,要求你找出其中最长的一条变异链。
在此假设给出的变异都是由突变引起的,不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来,并且不存在循环变异的情况。
输入格式:
输入在第一行中给出一个正整数 N(≤$10^4$),即病毒种类的总数。于是我们将所有病毒从 0 到 N?1 进行编号。
随后 N 行,每行按以下格式描述一种病毒的变异情况:
其中 k 是该病毒产生的变异毒株的种类数,后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒(0≤i<N)。题目保证病毒源头有且仅有一个。
输出格式:
首先输出从源头开始最长变异链的长度。
在第二行中输出从源头开始最长的一条变异链,编号间以 1 个空格分隔,行首尾不得有多余空格。如果最长链不唯一,则输出最小序列。
注:我们称序列{a1,…,an}比序列{b1,…,bn} “小”,如果存在 1≤k≤n 满足
$a^i$=$b^i$对所有 i<k 成立,且 $a^k$ < $b^k$。
输入样例:
1 2 3 4 5 6 7 8 9 10 11
| 10 3 6 4 8 0 0 0 2 5 9 0 1 7 1 2 0 2 3 1
|
输出样例:
思路
首先,读入题目中给的数据,建立树形关系,可以考虑用vector建立一个邻接表存储;然后,题目要求按照字典序最小的方式输出结果,所以需要在读入每一个点的子节点后,按照编号从小到大排个序,用sort就可以了。然后DFS搜一遍,找到最长变异链就可以了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #include<bits/stdc++.h> using namespace std; const int maxn = 10010; vector<int> v[maxn]; int n; unordered_set<int> s; vector<int> res; vector<int> temp; void dfs(int u) { if(!v[u].size()){ if(temp.size() > res.size()) res = temp; return; } for(int i=0;i<v[u].size();i++){ temp.push_back(v[u][i]); dfs(v[u][i]); temp.pop_back(); } } int main() { cin >> n; for(int i=0;i<n;i++){ int k; cin >> k; while(k -- ){ int x; cin >> x; s.insert(x); v[i].push_back(x); } sort(v[i].begin(),v[i].end()); } int root = 0; for(int i=0;i<n;i++){ if(!s.count(i)){ root = i; break; } } temp.push_back(root); dfs(root); cout << res.size() << endl; for(int i=0;i<res.size();i++){ if(i) cout << " "; cout << res[i]; } return 0; }
|