土下座しながら探索中

主に競技プログラミング

グラフ

SRM Div1 easy : BiconnectedDiv1

問題概要 : n個のノードが存在し、それらは0からn-1まで番号が割り振られているノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つまた、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ各辺は無向辺であるこのように…

SRM 692 Div1 easy : HardProof

問題概要 : 任意の2点間に辺があるような重み付き有向グラフが隣接行列Dとして与えられるこのグラフはn個の頂点から成り、各頂点には0から順にn-1まで番号が割り振られている全ての頂点を少なくとも1回以上訪れるような閉路について考えたとき、この閉路に…

SRM 691 Div1 easy : Sunnygraphs

問題概要 : n個の頂点とn本の無向辺があり、頂点は0からn-1まで番号が割り振られている また、辺は頂点iから頂点a[i]に向けて貼られている ( ただし、i != a[i] )このグラフに対して次の処理を行う 1. 新たな頂点 n を追加する 2. 0からn-1までの頂点集合か…

Codeforces 104C : Cthulhu

問題リンク : Problem - 104C - Codeforces問題概要 : 無向グラフがあたえられる このグラフに、ちょうど1つだけ閉路が存在するかどうか判定せよ解法 : まず、グラフが非連結な場合があるので最初にDFSやらなんやらして非連結ならNOと出力して終わる 次に、…