L2-038 病毒溯源

详解代码

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

using namespace std;

const int N = 10010,M=10010;

int n;
int h[N], e[M], ne[M], idx;//邻接表,h表示顶点，e表示当前边的终点，ne表示下一条边，idx当前边的编号
int son[N];//每个点的儿子是谁
bool st[N];//标记x是有父节点的,同时找哪个点是根节点

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    int res = 0;
    son[u] = -1;//这个点先不能往下走
    for (int i = h[u]; ~i; i = ne[i])//遍历u的所有子节点
    {
        int j = e[i];//j表示子节点的编号
        int d = dfs(j);//求一下从j往下走的最大长度是多少
        if (res < d) res = d, son[u] = j;//更新长度,u走到j这个点
        else if (res == d) son[u] = min(son[u], j);//如果长度相等,就更新成编号最小的
    }
    return res + 1;//加1是加上当前这个点
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表的表头
    cin>>n;
    
    //读入每个点的所以儿子
    for (int i = 0; i < n; i ++ )
    {
        int cnt;
        cin>>cnt;
        while(cnt--)
        {
            int x;
            cin>>x;
            add(i,x);
            st[x]=true;
        }
    }
    //找哪个点是根节点
    int root=0;
    while(st[root])root++;//如果root有父节点,说明root不是根节点,就往后走
    
    printf("%d\n", dfs(root));//最大长度
    printf("%d", root);//从根节点往下走
    while (son[root] != -1)//当根节点能往下走的时候
    {
        root = son[root];
        printf(" %d", root);
    }

    return 0;
}


//给一棵树找到从根节点到叶节点的最长路径,并输出,如果长度相同,输出字典序小的
//从根开始往下递归递归