L2-038 病毒溯源 - java

题目解析

给定n个病毒

求出 从源头开始最远的变异长度 及 字典序最小的变异链

解题思路

直接上图好理解这个

我们找到了根节点之后直接看里面 距离根节点的最长长度是多少 以及 字典序最小的序列

很显然 长度是4 变异链是 0 4 9 1

然后直接搜就完事了

我们先找出根节点是那个

然后从根节点开始往下搜

每次去记录要到最远距离的节点 也就是 变异链往下的最小节点

注: java 不知道为啥第5个测试数据一直出现答案错误

代码

java

import java.io.*;
import java.util.*;

public class Main
{
	static int N = (int) 1e4 + 10;
	static ArrayList<Integer> ar[] = new ArrayList[N];
	static int son[] = new int[N]; // 表示最后答案中 当前节点的子节点
	static boolean use[] = new boolean[N]; // 每个节点是否为非根节点

	static int dfs(int u)
	{
		int max = 0;
		son[u] = -1;
		for (int i = 0; i < ar[u].size(); i++)
		{
			int j = ar[u].get(i);

//			根节点到当前节点的距离
			int d = dfs(j);

//			如果 根节点到该节点的距离 大于 当前找到的最大
			if (d > max)
			{
				son[u] = j; // 父亲节点 的下一个节点 为 当前节点
				max = d; // 更新当前找到的最大值
			}
//			因为最后的输出需要字典序最小 所以需要最小的
			else if (d == max)
				son[u] = Math.min(son[u], j);
		}
		return max + 1;
	}

	public static void main(String[] args) throws IOException
	{
		int n = ini();
		for (int i = 0; i < n; i++)
		{
			ar[i] = new ArrayList<Integer>();
			int k = ini();
			while (k-- > 0)
			{
				int x = ini();
				ar[i].add(x);
				use[x] = true; // 标记这个点为非根节点
			}
		}

//		找根节点
		int root = 0;
		while (use[root])
			root++;

//		初始化
		Arrays.fill(son, -1);

//		输出距离根节点最远的距离
		out.println(dfs(root));

		out.print(root);
		root = son[root];
		while (root != -1)
		{
			out.print(" " + root);
			root = son[root];
		}

		out.flush();
		out.close();
	}
    
	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

}

c++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e4 + 10;
vector<int> ar[N];
int son[N];
bool use[N];

int dfs(int u)
{
    int max = 0;
    son[u] = -1;
    for(int i = 0; i < ar[u].size(); i ++)
    {
        int j = ar[u][i];
        int d = dfs(j);
        if(d > max)
        {
            son[u] = j;
            max = d;
        }
        else if(d == max)
            son[u] = min(son[u], j);
    }
    return max + 1;
}

int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int k; cin >> k;
        while(k -- > 0)
        {
            int x; cin >> x;
            ar[i].push_back(x);
            use[x] = true;
        }
    }
    
    int root = 0;
    while(use[root]) root++;
    
    for(int i = 0; i < n; i ++) son[i] = -1;
    
    cout << dfs(root) << endl;
    
    cout << root;
    root = son[root];
    while(root != -1)
    {
        cout << " " << root;
        root = son[root];
    }
    
    return 0;
}

ArrayList
ArrayList

fill
fill

团体程序设计天梯赛-练习集-java