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;
}
//给一棵树找到从根节点到叶节点的最长路径,并输出,如果长度相同,输出字典序小的
//从根开始往下递归递归
原文地址:https://blog.csdn.net/2301_79203206/article/details/139196549
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!