L2-026 小字辈 (25 分)

原题连接

题意

找最底层的叶子节点

思路

根据题意，输入一个数组a[i]，第i个数的父亲是a[i]，祖宗节点的父亲是-1，那么就可以根据这种方案建图。i为父节点，a[i]为子节点。

坑点

暂无

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int res[N];
int n;
vector<int> g[N];
void dfs(int u, int cnt) //分别记录当前到那个点和第几层
{
    
	res[u] = cnt;//标记第几层
	for (int i = 0; i < g[u].size(); i ++ )
	{
    
		int j = g[u][i];
		dfs(j, cnt + 1);
	}
}
int main(int argc, char const *argv[])
{
    
	int h;
	cin >> n;
	for (int i = 1; i <= n; i ++ )
	{
    
		cin >> a[i];
		if (a[i] == -1) //确定祖宗节点
		{
    
			h = i;
			continue;
		}
		g[a[i]].push_back(i); //a[i]的子节点有i
	}
	dfs(h, 1);//从祖宗节点开始往下遍历
	vector<int> ans;
	int maxn = -0x3f3f3f3f;//找最大值
	for (int i = 1; i <= n; i ++ )
	{
    
		if (res[i] == maxn)//一样的就直接加入
		{
    
			ans.push_back(i);
		}
		else if (res[i] > maxn)//如果更新了最大值，需要清空，再加入
		{
    
			maxn = res[i];
			ans.clear();
			ans.push_back(i);
		}
	}
	cout << maxn << endl;
	for (int i = 0; i < ans.size(); i ++ ) 
	{
    
		cout << ans[i];
		if (i != ans.size() - 1) cout << " ";
	}				
	return 0;
}