9170 | 2024. 02. 16 18:55:34 | NagyLeo | Testnevelés óra | python3 | Elfogadva 50/50 | 902ms | 82708 KiB |
from sys import stdin, stdout
input=stdin.readline
def solv():
N, K = map(int, input().split())
graph = [[] for i in range(N + 1)]
indeg = [0] * (N + 1)
for i in range(K):
a, b = map(int, input().split())
graph[a].append(b)
indeg[b] += 1
zero = []
# a --> b --> 2 <-- c
# \-> d
for i in range(1, N + 1):
if indeg[i] == 0:
zero.append(i)
# print(parents)
result = [zero[:]]
seen = len(zero)
while zero:
tmp = []
for i in zero:
for j in graph[i]:
indeg[j] -= 1
if indeg[j] == 0:
tmp.append(j)
if tmp:
result.append(tmp[:])
seen+=len(tmp)
zero = tmp
# print(result,graph)
if seen != N:
print("0")
return
if len(result) == N:
print("1")
for i in result:
print(*i, end=" ")
else:
# result=[ [1,2,3], [4,5]]
print("2")
for i in result:
print(*i, end=" ")
print()
for i in result:
print(*i[::-1], end=" ")
solv()
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 18ms | 11288 KiB | |||
2 | Elfogadva | 0/0 | 17ms | 11796 KiB | |||
3 | Elfogadva | 0/0 | 490ms | 49620 KiB | |||
4 | Elfogadva | 2/2 | 17ms | 11948 KiB | |||
5 | Elfogadva | 3/3 | 17ms | 12348 KiB | |||
6 | Elfogadva | 3/3 | 18ms | 12672 KiB | |||
7 | Elfogadva | 3/3 | 17ms | 12588 KiB | |||
8 | Elfogadva | 1/1 | 18ms | 13000 KiB | |||
9 | Elfogadva | 3/3 | 18ms | 13244 KiB | |||
10 | Elfogadva | 3/3 | 23ms | 13556 KiB | |||
11 | Elfogadva | 3/3 | 25ms | 13908 KiB | |||
12 | Elfogadva | 1/1 | 21ms | 13396 KiB | |||
13 | Elfogadva | 2/2 | 24ms | 14232 KiB | |||
14 | Elfogadva | 3/3 | 20ms | 14328 KiB | |||
15 | Elfogadva | 1/1 | 418ms | 47776 KiB | |||
16 | Elfogadva | 3/3 | 404ms | 56832 KiB | |||
17 | Elfogadva | 5/5 | 266ms | 70432 KiB | |||
18 | Elfogadva | 1/1 | 646ms | 82368 KiB | |||
19 | Elfogadva | 2/2 | 425ms | 49036 KiB | |||
20 | Elfogadva | 3/3 | 786ms | 82584 KiB | |||
21 | Elfogadva | 4/4 | 783ms | 82556 KiB | |||
22 | Elfogadva | 4/4 | 902ms | 82708 KiB |