AcWing 3465. 病毒溯源
原题链接
中等
作者:
东方晓
,
2021-07-22 09:44:00
,
所有人可见
,
阅读 363
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int h[N], e[N], ne[N], idx;
int son[N];
bool st[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u){ //树形DP
int res = 0; //记录最长分枝的结点数目
son[u] = -1; //记录路径
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
int d = dfs(j);
if (res < d) res = d, son[u] = j;
else if (res == d) son[u] = min(son[u], j);
}
return res + 1;
}
int main(){
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++ ){
int cnt;
scanf("%d", &cnt);
while (cnt -- ){
int x;
scanf("%d", &x);
add(i, x);
st[x] = true; //标记
}
}
int root = 0;
while (st[root]) root ++ ;
printf("%d\n", dfs(root));
printf("%d", root);
while (son[root] != -1){
root = son[root];
printf(" %d", root);
}
return 0;
}