search

kemuniku / cplib

Creative Commons Zero v1.0 Universal
4 stars 1 forks source link

DAGの到達可能性クエリ #437

Open kemuniku opened 1 month ago

kemuniku commented 1 month ago

N頂点M辺の有向グラフが与えられます。以下のクエリにQ個答えてください。 頂点aから頂点bに行くことができますか？

解法 クエリ先読みbitset 後ろから順にbitsetでどこの頂点にいけるかを持ちながらDFS O(N^2/w + Q)？

kemuniku commented 1 month ago

よ～するにこれです https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0275