统计后台网站有哪些,大学生网站设计,苏州教育学会网站建设,品牌网站建设要多少钱L2-026 小字辈 时间限制 400 ms 内存限制 64 MB 题目描述#xff1a;
本题给定一个庞大家族的家谱#xff0c;要请你给出最小一辈的名单。
输入格式#xff1a; 输入在第一行给出家族人口总数 N#xff08;不超过 100 000 的正整数#xff09; —— 简单起见#xff0c…L2-026 小字辈 时间限制 400 ms 内存限制 64 MB 题目描述
本题给定一个庞大家族的家谱要请你给出最小一辈的名单。
输入格式 输入在第一行给出家族人口总数 N不超过 100 000 的正整数 —— 简单起见我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式 首先输出最小的辈分老祖宗的辈分为 1以下逐级递增。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔行首尾不得有多余空格。
输入样例 9 2 6 5 5 -1 5 6 4 7 输出样例 4 1 9 给定n个数第i个编号代表第i个人的父母 让你求出最小的辈分以及最小辈分的成员编号 emmmmmmm
1、dfs搜索 先找出根节点然后依据根节点往下建树 统计并更新最下面的叶子节点
2、并查集 可以利用并查集去实现找爹爹的同时辈分加起来 1、dfs搜索
java 过不了欸
import java.io.*;
import java.math.*;
import java.util.*;public class Main
{static int N (int) 1e5;static ArrayListInteger map[] new ArrayList[N 10];static HashSetInteger set new HashSetInteger();static int maxDeep 0;// node节点 deep辈分static void dfs(int node, int deep){
// 同辈份if (deep maxDeep) set.add(node);
// 找到再小的辈分else if (deep maxDeep){
// 更新最小的辈分maxDeep deep;set.clear();set.add(node);}// 遍历该辈分下的孩子for (int i 0; i map[node].size(); i)dfs(map[node].get(i), deep 1);}public static void main(String[] args){int n sc.nextInt();for (int i 1; i n; i)map[i] new ArrayListInteger();int root -1;for (int i 1; i n; i){int x sc.nextInt();
// 找到老祖宗if (x -1){root i;continue;}map[x].add(i);}dfs(root, 1);out.println(maxDeep);int count 0;for (int i : set){if (count ! 0)out.print( );out.print(i);}out.flush();out.close();}static Scanner sc new Scanner(System.in);static PrintWriter out new PrintWriter(System.out);
}
c
#include bits/stdc.husing namespace std;const int N 1e5;
vectorint mp[N 10];
setint s;
int maxDeep 1;void dfs(int node, int deep)
{if(deep maxDeep)s.insert(node);else if(deep maxDeep){s.clear();s.insert(node);maxDeep deep;}for(int i 0; i mp[node].size(); i )dfs(mp[node][i], deep 1);
}int main()
{int n; scanf(%d, n);int root -1;for(int i 1; i n; i ){int x; scanf(%d, x);if(x -1){root i;continue;}mp[x].push_back(i);}dfs(root, 1);printf(%d\n, maxDeep);for(auto it s.begin(); it ! s.end(); it ){if(it ! s.begin())printf( );printf(%d, *it);}return 0;
}2、 并查集
java 还不是不知道为啥错了两个点
import java.io.*;
import java.math.*;
import java.util.*;public class Main
{static int N (int) 1e5;static int shu[] new int[N 10];static int deep[] new int[N 10];static int find(int x){
// 祖宗节点if (shu[x] -1)deep[x] 1;// 当前的辈分需要更新if (deep[x] 0)deep[x] find(shu[x]) 1;return deep[x];}public static void main(String[] args){int n sc.nextInt();for (int i 1; i n; i)shu[i] sc.nextInt();int max 1;for (int i 1; i n; i)max Math.max(max, find(i));out.println(max);int cnt 0;for (int i 1; i n; i){if (max deep[i]){if (cnt ! 0)out.print( );out.print(i);}}out.flush();out.close();}static Scanner sc new Scanner(System.in);static PrintWriter out new PrintWriter(System.out);
}
c
#include bits/stdc.husing namespace std;const int N 1e5;
int shu[N 10];
int deep[N 10];int find(int x)
{if(shu[x] -1)deep[x] 1;if(deep[x] 0)deep[x] find(shu[x]) 1;return deep[x];
}int main()
{int n; scanf(%d, n);for(int i 1; i n; i )scanf(%d, shu[i]);int mx 1;for(int i 1; i n; i ) mx max(mx, find(i));printf(%d\n, mx);int cnt 0;for(int i 1; i n; i ){if(deep[i] mx){if(cnt ! 0)printf( );printf(%d, i);}}return 0;
}ArrayList ArrayList
dfs dfs
并查集 并查集 如果有说错的 或者 不懂的 尽管提 嘻嘻
一起进步 闪现
