7K12 blog

猫でも分かる何か

2022-05-02から1日間の記事一覧

NyaaLIB::GT_SCC

Strongly Connected Components(強連結成分分解)計算量 https://atcoder.github.io/ac-library/production/document_ja/scc.html run(void) 有向グラフを強連結成分分解する 戻り値 g: 強連結成分分解した隣接リスト groups: 閉路毎の頂点集合(トポロジカ…

NyaaLIB::GTL_BFS

BFS(幅優先探索)計算量 BFS開始頂点は複数になることも多いので配列を渡す 昇順に頂点を遷移したいときは queue を priority_queue にする std::queue<long long> q; → std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq; #include <bits/stdc++.h> namespace NyaaLIB { struct BFS_ARG { using</bits/stdc++.h></long></long></long>…