GRL_4_B Topological Sort

C

問題トポロジカルソート | グラフ | Aizu Online Judgeトポロジカルソートの問題です。名前は聞いたことがあったのですが、初挑戦。こちらのページを参考にしました。トポロジカルソート - ferinの競プロ帳１．各ノードに自分に向かう辺の数（入次数）を…

2018-05-21

GRL_4_A Cycle Detection for a Directed Graph

C

問題有向グラフの閉路検知 | グラフ | Aizu Online Judge有効グラフの閉路の有無を検出する問題です。各頂点からdfs→途中でスタートの頂点を通過したら閉路ありという感じで実装しました。頂点の数も少ないので、TLEせず一発okでした。 #include<stdio.h> #include<stdlib.h></stdlib.h></stdio.h>…

2018-05-21

ALDS1_11_D Connected Components

C

問題グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge連結生成分解の問題。GRL_3_Cの"強"連結生成分解の問題を解いたのですが、TLEとなってしまいました。じゃあALDSの連結生成分解ならできるんじゃね？ってことで挑戦したら解けました。…

2018-05-21

GRL_2_A Minimum Spanning Tree

C

問題最小全域木 | グラフ | Aizu Online Judge以前記事にした最小全域木の問題とほとんど同じです。頂点の数が以前のものより多く、隣接行列ではメモリ不足になるので、隣接リストを用いました。アルゴリズム自体はプリムのやつです。 #include<stdio.h> #include<stdlib.h> #</stdlib.h></stdio.h>…