92 lines
1.6 KiB
Python
92 lines
1.6 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
import queue
|
||
|
|
|
||
|
|
def criteria(a):
|
||
|
|
return a[0]
|
||
|
|
|
||
|
|
def promote(G, Ginv, a, b):
|
||
|
|
Depth = [None] * len(G)
|
||
|
|
|
||
|
|
Q = queue.Queue(maxsize=len(G))
|
||
|
|
|
||
|
|
print(Ginv)
|
||
|
|
|
||
|
|
for i in range(len(G)):
|
||
|
|
if len(Ginv[i]) == 0:
|
||
|
|
Q.put(i)
|
||
|
|
Depth[i] = 0
|
||
|
|
|
||
|
|
print(G)
|
||
|
|
|
||
|
|
while not Q.empty():
|
||
|
|
u = Q.get()
|
||
|
|
for v in G[u]:
|
||
|
|
if Depth[v] is None:
|
||
|
|
Depth[v] = Depth[u] + 1
|
||
|
|
Q.put(v)
|
||
|
|
|
||
|
|
for i in range(len(Depth)):
|
||
|
|
Depth[i] = (Depth[i], i)
|
||
|
|
|
||
|
|
print(Depth)
|
||
|
|
|
||
|
|
Depth.sort(key=criteria, reverse=True)
|
||
|
|
|
||
|
|
sums = [0]
|
||
|
|
p = None
|
||
|
|
for i in range(0, len(Depth)):
|
||
|
|
if p is None or p == Depth[i][0]:
|
||
|
|
sums[-1] += 1
|
||
|
|
p = Depth[i][0]
|
||
|
|
else:
|
||
|
|
sums.append(0)
|
||
|
|
p = None
|
||
|
|
|
||
|
|
ss = 0
|
||
|
|
i = 0
|
||
|
|
while i < len(sums) and ss + sums[i] <= a:
|
||
|
|
ss = ss + sums[i]
|
||
|
|
i += 1
|
||
|
|
|
||
|
|
prom_A = ss
|
||
|
|
|
||
|
|
while i < len(sums) and ss + sums[i] <= b:
|
||
|
|
ss = ss + sums[i]
|
||
|
|
i += 1
|
||
|
|
|
||
|
|
prom_B = ss
|
||
|
|
|
||
|
|
if ss < b:
|
||
|
|
ss = ss + sums[i]
|
||
|
|
|
||
|
|
no_prom = ss
|
||
|
|
|
||
|
|
return (prom_A, prom_B, no_prom)
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
s = input().split()
|
||
|
|
a = int(s[0])
|
||
|
|
b = int(s[1])
|
||
|
|
n_emp = int(s[2])
|
||
|
|
n_prec = int(s[3])
|
||
|
|
|
||
|
|
G = []
|
||
|
|
Ginv = []
|
||
|
|
for i in range(n_emp):
|
||
|
|
G.append([])
|
||
|
|
Ginv.append([])
|
||
|
|
|
||
|
|
for i in range(n_prec):
|
||
|
|
s = input().split()
|
||
|
|
x = int(s[0])
|
||
|
|
y = int(s[1])
|
||
|
|
G[x].append(y)
|
||
|
|
Ginv[y].append(x)
|
||
|
|
|
||
|
|
x, y, z = promote(G, Ginv, a, b)
|
||
|
|
print(x)
|
||
|
|
print(y)
|
||
|
|
print(z)
|
||
|
|
|