競技プログラミング風 C++問題集【第14回】


目次

無向グラフ(難易度:★★★☆☆)

問題

複数の頂点と2つの頂点を結ぶ複数の辺から構成され、辺が両端の頂点から互いの相手の頂点に移動可能なものを「無向グラフ」と呼ぶ。

無向グラフの状態を表すクラスを UndirGraph とするとき、以下のメンバ関数を実装しなさい。

・頂点 v1 と v2 を引数にとり、それらの間に辺を追加する void addEdge(int v1, int v2)
・頂点 v1 と v2 を引数にとり、それらの間の距離を返す int dist(int v1, int v2)
・グラフが閉路を持つかどうかを返す bool hasCycle()

ただし、連結している頂点間距離はすべて1とする。
例えば、下図のような場合、v1, v2 間の距離は5となる。

競技プログラミング風C++問題集【第14回】_01

また、「閉路」とはある頂点から同じ頂点を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++問題集【第16回】

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

競技プログラミング風 C++問題集【第15回】

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

競技プログラミング風 C++問題集【第14回】

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第13回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

競技プログラミング風 C++問題集【第12回】

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第11回】

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

競技プログラミング風 C++問題集【第10回】

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

競技プログラミング風 C++問題集【第9回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

競技プログラミング風 C++問題集【第8回】

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

競技プログラミング風 C++問題集【第7回】

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP