求助
  • 板块学术版
  • 楼主chensiru
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/8 14:37
  • 上次更新2023/11/3 11:03:26
查看原帖
求助
817525
chensiru楼主2023/7/8 14:37

题目描述

小明一家在一个巨大的城堡里,古堡里有N 个房间,有些房间之间有过道相连,城堡里一共有N-1 条道,通过这些过道,小明可以从任一间房间走到另外一间房间。由于城堡建在山上,所以小明需要考虑安全防护问题,G 公司现在有一款安全产品,只要在一个房间里面安装,就可以监控和这房间连接的所有过道,但是这人产品非常贵,所以小明要节约一点使用。他想知道,至少要安装多少套产品,就可以把所有的过道都监控起来。

输入

第一行一个整数 N,表示房间的数量 第二行到第 N+1行,每行描述一个房间的信息,依次为:该房间的编号,相接的过道数量k,接下来k个整数,分别是

r1,r2,⋯ ,rkr_{1},r_{2},\cdots,r_{k}

每条过道的另一个房间的编号对于每一条过道,在输入中只会出现一次、也就是说,对于连接两房间的过道,要么在x房间的信息中出现,要么在y房间的信息中出现

输出

一个整数,表示至少需要安装安全产品的套数

2023/7/8 14:37
加载中...