• L2-026 小字辈 - java


    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 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);
    }
    
    
    • 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
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    c++

    #include 
    
    using namespace std;
    
    const int N = 1e5;
    vector mp[N + 10];
    set 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;
    }
    
    • 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
    • 51

    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);
    }
    
    
    • 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
    • 51
    • 52

    c++

    #include 
    
    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;
    }
    
    • 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

    ArrayList
    ArrayList

    dfs
    dfs

    并查集
    并查集


    如果有说错的 或者 不懂的 尽管提 嘻嘻

    一起进步!!!


    闪现

  • 相关阅读:
    【腾讯云HAI域探秘】0基础也能开发应用
    STM32内部Flash的使用
    一文读懂 Golang init 函数执行顺序
    【最多等和不相交连续子序列】python实现-附ChatGPT解析
    iLogtail 社区版使用入门 - 采集 MySQL Binlog
    Centos8上部署MySQL主从备份
    杭电多校杂题收录
    6.3二叉树的层序遍历(LC102,LC107-M)
    Java语法详解
    heic图片如何转为jpg格式
  • 原文地址:https://blog.csdn.net/weixin_52136008/article/details/134047011