目次
無向グラフ(難易度:★★★☆☆)
問題
複数の頂点と2つの頂点を結ぶ複数の辺から構成され、辺が両端の頂点から互いの相手の頂点に移動可能なものを「無向グラフ」と呼ぶ。
無向グラフの状態を表すクラスを UndirGraph とするとき、以下のメンバ関数を実装しなさい。
・頂点 v1 と v2 を引数にとり、それらの間に辺を追加する void addEdge(int v1, int v2)
・頂点 v1 と v2 を引数にとり、それらの間の距離を返す int dist(int v1, int v2)
・グラフが閉路を持つかどうかを返す bool hasCycle()
ただし、連結している頂点間距離はすべて1とする。
例えば、下図のような場合、v1, v2 間の距離は5となる。
また、「閉路」とはある頂点から同じ頂点を2回以上訪れず、2つ以上の頂点を経由して元に戻ってくる経路(サイクルとも呼ばれる)のこととする。 要するにループのことであり、上図のv2の右おより下部分が閉路である。
データ構造としては、vector<vector<int>> m_vertex; で、各頂点に連結している頂点リストを表すものとする。 読者がこれ以外のデータ構造を用いたい場合は、変更してもかまわない。
#include <iostream> // 標準入出力ライブラリ #include <string> #include <vector> using namespace std; // std 名前空間使用 #define DO_TEST(exp) do_test(exp, __LINE__) void do_test(bool b, int line) { if( b ) return; // OK cout << "\nNG at line " << line << "\n"; exit(1); } class UndirGraph { public: UndirGraph() {} public: string print() const { string txt; int i = 0; for(const auto&lst: m_vertex) { txt += to_string(i++) + ": "; for(auto x: lst) { txt += to_string(x) + ", "; } txt += "\n"; } return txt; } void addEdge(int v1, int v2) { // 頂点 v1, v2 を連結, v1, v2 は 0 オリジン // ToDo: } int dist(int v1, int v2) const { // 頂点 v1, v2 の距離を求める。非連結の場合は -1 を返す // ToDo: return 0; } bool hasCycle() const { // 巡回路があるか? // ToDo: return false; } private: vector<vector<int>> m_vertex; // 頂点に連結している頂点リスト }; int main() { UndirGraph ug; ug.addEdge(0, 1); ug.addEdge(0, 4); ug.addEdge(1, 2); ug.addEdge(1, 3); ug.addEdge(1, 4); ug.addEdge(2, 3); ug.addEdge(2, 5); ug.addEdge(3, 4); cout << ug.print(); // DO_TEST( ug.dist(0, 1) == 1 ); DO_TEST( ug.dist(0, 2) == 2 ); DO_TEST( ug.dist(0, 3) == 2 ); DO_TEST( ug.dist(0, 4) == 1 ); DO_TEST( ug.dist(0, 5) == 3 ); DO_TEST( ug.dist(2, 4) == 2 ); // DO_TEST( ug.hasCycle() ); if (1) { UndirGraph ug; ug.addEdge(0, 1); ug.addEdge(0, 4); ug.addEdge(1, 2); ug.addEdge(3, 4); DO_TEST(!ug.hasCycle()); } if (1) { UndirGraph ug; ug.addEdge(0, 1); ug.addEdge(1, 2); ug.addEdge(2, 3); ug.addEdge(3, 0); DO_TEST(ug.hasCycle()); } if (1) { UndirGraph ug; ug.addEdge(1, 2); ug.addEdge(2, 3); ug.addEdge(3, 1); DO_TEST(ug.hasCycle()); } cout << "\nGood Job!\n"; return 0; }
競技プログラミング風 標準C++ライブラリ入門 連載目次リンク
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |