网站建设交付形式,互动平台网站建设,微信客户联系方式,wordpress 网站备案号文章目录 查找一个有向网络的头节点和尾节点幼儿园篮球游戏 查找一个有向网络的头节点和尾节点
在一个有向图中#xff0c;有向边用两个整数表示#xff0c;第一个整数表示起始节点#xff0c;第二个整数表示终止节点#xff1b;图中只有一个头节点#xff0c;一个或者多… 文章目录 查找一个有向网络的头节点和尾节点幼儿园篮球游戏 查找一个有向网络的头节点和尾节点
在一个有向图中有向边用两个整数表示第一个整数表示起始节点第二个整数表示终止节点图中只有一个头节点一个或者多个尾节点图可能存在环有环则输出-1输出图中的头节点入度为0、尾节点出度为0如图头节点为1尾节点为4。 输入描述 第一行输入nn 0 第二行为n个数对表示n条边 输出描述 输出一行头节点、尾节点以空格隔开多个尾节点则从大到小输出。 示例1 输入 4 1 2 1 3 2 4 3 4 输出 1 4
思路
拓扑排序判断有向图是否有环有环则直接输出-1只有一个起始点一个或多个结尾点
relations {}
indegree {}
head -1
tails []def find_head():global relations,indegree,headfor keys in relations:if (keys in indegree) :continueelse :head keysbreakdef find_tails():global relations,indegree,tailsfor keys in indegree :if (keys in relations) :continueelse :tails.append(keys)n int(input())
nums [int(x) for x in input().split( )]i0
while(i 2 * n):if(nums[i] in relations):relations[nums[i]].append(nums[i 1])else :relations[nums[i]] []relations[nums[i]].append(nums[i 1])if(nums[i 1] in indegree):indegree[nums[i 1]] 1else :indegree[nums[i 1]] 1i 2find_head()
find_tails()
tails.sort()queue []
queue.append(head)
while (True) :if(len(queue)0):breakelse :temp queue[0]queue.pop(0)if(temp in relations):temp_list relations[temp]for x in temp_list:indegree[x] indegree[x] - 1if (indegree[x] 0) :queue.append(x)
flag 1
for key in indegree:if (indegree[key] 0) :flag 0if (flag0) :print(-1)
else: output_str str(head) for x in tails:output_str str(x) print(output_str[:-1])幼儿园篮球游戏 双指针 线性表
import functools
import sys
import copy
import re
import mathnums [int(x) for x in input().split(,)]
target_nums [int(x) for x in input().split(,)]arr [float(inf) for i in range(300)]left 0
right 0
target_pos 0result
i0
while(True):if(ilen(nums)):breakelse :arr[right] nums[i]right1while (True) :if(right left):breakelse :if (arr[left] target_nums[target_pos]) :result Lleft 1target_pos 1continueelif (arr[right-1] target_nums[target_pos]) :result Rright - 1target_pos 1continuebreaki1if (left ! right) :print(NO)
else :print(result)
