桂林网站制作网站,嘉兴个人建站,制图平台,公司建的站加油违法吗题目描述
小明的实验室有 N 台电脑#xff0c;编号 1⋯N。原本这 N 台电脑之间有 N−1 条数据链接相连#xff0c;恰好构成一个树形网络。在树形网络上#xff0c;任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时#xff0c;管理员误操作使得某两台电脑之间…题目描述
小明的实验室有 N 台电脑编号 1⋯N。原本这 N 台电脑之间有 N−1 条数据链接相连恰好构成一个树形网络。在树形网络上任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时管理员误操作使得某两台电脑之间增加了一条数据链接于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径使得这些电脑上的数据传输出现了 BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑你能帮助他吗
输入描述
输入范围
第一行包含一个整数 N 。
以下 N 行每行两个整数 a,b表示 a 和 b 之间有一条数据链接相连。
其中 1≤N≤10^51≤a,b≤N。
输入保证合法。
输出描述
按从小到大的顺序输出在环路上的电脑的编号中间由一个空格分隔。
输入输出样例
示例 输入 5
1 2
3 1
2 4
2 5
5 3输出 1 2 3 5 思路
正常链接状态 1、树状连接网络每个节点只有一个父节点 2、若一个父节点的子节点被发现已经标记则该子节点一定在环上深度优先搜索过程中查找已经标记的点 参考代码
N int(input())
edge [[] for i in range(N1)] #邻接表
pre [0] * (N1)
ring [] #保存以后的节点
vis [False] * (N1)
for i in range(N):u, v map(int, input().split())edge[u].append(v)edge[v].append(u)def dfs(x,father): # x 表示当前节点father表示父亲节点vis[x] True #标记for son in edge[x]: # son 子节点if len(ring) 0: #是否被标记returnif not vis[son]: #判断子节点是否访问过pre[son] x #父节点等于当前节点dfs(son, x) elif son ! father: #子节点不等于父亲节点tmp xwhile tmp ! son:ring.append(tmp)tmp pre[tmp]ring.append(son)
dfs(1, 0)
ring.sort()
for k in ring: print(k,end )
