题目描述
用python写了c++的bitset算法,结果是对的,但还是超时了
样例
#相当于c++的或运算
def bitCal(father, son):
cnt=0
for f,s in zip(father,son):
if f or s:father[cnt]=1
cnt+=1
return father
from collections import deque
nodes, edges = map(int, input().split())
graph=dict((u,[]) for u in range(1,nodes+1))
inDegree=dict((u,0) for u in graph)
#邻接字典
for i in range(edges):
st,en=map(int, input().split())
if en not in graph[st]:graph[st].append(en)
#入度
for u in graph.keys():
values=graph[u]
for val in values:inDegree[val]+=1
d=deque([u for u in inDegree if not inDegree[u]])
#计算正序拓扑
res=[]
while d:
cur=d.popleft()
res.append(cur)
for node in graph[cur]:
inDegree[node]-=1
if not inDegree[node]:d.append(node)
res.reverse()
vexLen = len(res)
#位运算数组
bitlst=[]
for i in range(vexLen+1):bitlst.append([0 for j in range(vexLen+1)])
#遍历
for node in res:
bitlst[node][node] = 1
for nod in graph[node]:
bitlst[node]=bitCal(bitlst[node], bitlst[nod])
for item in bitlst[1:]:
print(item.count(1))
```