Задача на ориентированный граф

Нужна помощь, почему код ниже не работает. (заваливает тест)


with open('INPUT.TXT') as f:
	N, K = f.readline().split()
	A = f.read().split()

N, K = int(N), int(K)

P = [[int(A[2 * i]), int(A[2 * i + 1])] for i in range(int((len(A) - 1) / 2))]
G = {x: [] for x in range(1, N + 1)}

for el in P:
	G[el[0]].append(el[1])

if len(P) < N - 1:
	ans = 'No'
else:
	s = 0
	for el in P:
		if el[1] == K:
			s = 1
			break
	if s == 1:
		ans = 'No'
	else:
		ans = 'Yes'
print(ans)

Комментарий к коду:
G = граф в котором если AB, то лошадь A быстрее B, тогда понятно что если в G меньше чем N - 1 вершин, то информации недостаточно.
Также понятно что граф ацикличен, в противном случае одна лошадь одновременно быстрее и медленее другой, соответственно в нем не более N - 1 ребра.
Остается случай когда ровно N - 1 ребро, несложно понять что он связный, потому достаточно удостоверится в том что indeg(K) \equiv0

А сколько тестов проходит код? Есть возможность узнать какой тест?

1 симпатия

проходит 4 теста, сайт не позволяет узнать(

1 симпатия

Нет, он может быть не связным.
Например тест:
4 1
1 2
1 3
2 3
0

В графе N - 1 ребро, и он не содержит противоречивой информации, но граф несвязный.

или вот так:

4 1
1 2
2 3
4 2
0

Граф связный, но не все вершины достижимы из 1

3 симпатии

Хорошо понял, спасибо

Можете на этот код посмотреть, он очевидно рабочий, но memory limit не влезает, что именно съедает так много памяти?

def gege(n, G):
	if len(G[n]) == 0:
		return []
	s = [el for el in G[n]]

	for el in G[n]:
		s += gege(el, G)
	return s


with open('INPUT.TXT') as f:
	N, K = f.readline().split()
	A = f.read().split()

N, K = int(N), int(K)

P = [[int(A[2 * i]), int(A[2 * i + 1])] for i in range(int((len(A) - 1) / 2))]
G = {x: [] for x in range(1, N + 1)}

for el in P:
	G[el[0]].append(el[1])

if len(set(gege(K, G))) == N - 1:
	ans = 'Yes'

else:
	ans = 'No'

print(ans)

image

1 симпатия

попробуй вместо того чтобы возвращать set вершин, хранить глобальный массив, и в нём помечать был ли ты в вершине или нет.

1 симпатия

спасибо, с памятью помогло, но теперь тайм лимит, у вас есть идеи по этому?
image

Не посещай те вершины в которых ты уже был.

3 симпатии

Действительно, спасибо!

© 2021-2022 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)