题目解析
给定n个数，第i个编号代表第i个人的父母
让你求出最小的辈分以及最小辈分的成员编号
解题思路
1、dfs搜索
先找出根节点，然后依据根节点往下建树
统计并更新最下面的叶子节点
2、并查集
可以利用并查集去实现，在找爹爹的同时把辈分加起来
代码
1、dfs搜索
java 过不了，欸，TLE+WA
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e5;
static ArrayList<Integer> map[] = new ArrayList[N + 10];
static HashSet<Integer> set = new HashSet<Integer>();
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 ArrayList<Integer>();
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++.h>
using namespace std;
const int N = 1e5;
vector<int> mp[N + 10];
set<int> 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 还不是不知道为啥超时了两个点。TLE
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++.h>
using 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;
}