2016-06-13

Bridge

競プロ Algorithm

グラフ構造において強連結を求めて処理することは多いけど、蟻本に載っているタイプのScc*1だと後の処理が結構使い辛い気がしてた。単にSccするだけならば別に良いんだけど、辺に対して操作をする時、その辺は強連結をするための辺なのか強連結成分同士を繋ぐ辺なのかの判定が面倒だったり、橋だけほしいのに実装の重いSccを書いてから求めるとか、結構だるい(自己基準)。

グラフにおける橋

グラフ内で削除すると到達不可能な頂点が出る辺を橋といって、求めるのに方法は色々とあるんだけど意外と書いてない。ただ、日本語の記事だといい感じに説明されたものもあるので、アルゴリズムの詳細は以下の記事を参考にしてほしい。

橋（bridge）検出アルゴリズム - nupiocaの日記

実装

上記記事の実装だと、from, toのペアが帰ってきていて、辺の判断が辛そうであったので橋の情報の持ち方を変更して行列に置換した。基本的に(個人の)Sccのライブラリと共存できそうな構造体を定義して、いい感じに。アルゴリズムの変更点は無い。

Raw source code

/*
  0-origin
*/

template<int V>
struct Bridge {
    int low[V], pre[V], cnt;
    vector<int> edge[V];
    bool res[V][V];

    void init() {
        cnt = 0;
        memset(low, 0, sizeof(low));
        memset(pre, 0, sizeof(pre));
        memset(res, false, sizeof(res));
        for (int i=0; i<V; i++) edge[i].clear();
    }

    void add_edge(int from, int to) {
        edge[from].push_back(to);
    }

    void add_edge_multi(int from, int to) {
        add_edge(from, to);
        add_edge(to, from);
    }

    int dfs(int cur, int from) {
        low[cur] = pre[cur] = ++cnt;

        for (int i=0; i<edge[cur].size(); i++) {
            int to = edge[cur][i];

            if (!pre[to]) {
                low[cur] = min(low[cur], dfs(to, cur));

                if (pre[to] == low[to]) {
                    res[cur][to] = true;
                }
            } else if (from != to) {
                low[cur] = min(low[cur], low[to]);
            }
        }

        return low[cur];
    }

    void build(int n) {
        for (int i=0; i<n; i++) {
            if (!pre[i]) dfs(i, i);
        }
    }
};

*1:強連結成分分解, Stronglu Connected Components

2015-09-20

個人用ブログテーマ設定

環境構築

公式テーマにあまり心惹かれるものがなかったので、cssを書き換える感じで現在のテーマに改変してみた。

最終更新日時: 2018/11/08

/* <system section="theme" selected="life"> */
@import url("/css/theme/life/life.css");
/* </system> */

@media (min-width: 1020px)
#container, #footer {
    width: 960px;
}

.entry-content, .entry-footer {
    max-width: 800px;
}

.categories a {
    border: none;
    background-color: #F5F7FA;
    font-size: 80% !important;
}

pre.code {
    font-size: 80% !important;
}

h1 a, h2 a, h3 a, h4 a, h5 a {
    border-bottom: none !important;
}

.embed-card{
    max-width: 100% !important;
}

2015-03-20

INSTALL HASKELL for OSX Yosemite

環境構築

環境は OSX Yosemite 10.10.1 です。
※brewのインストールなどは済んでいるものとして進める。

How to install

少し前までは

$ brew install haskell-platform

でインストール可能だったが、現在はできない。

$ brew install haskell-platform
Error: No available formula for haskell-platform
We no longer package haskell-platform. Consider installing ghc
and cabal-install instead:
  brew install ghc cabal-install

A binary installer is available:
  https://www.haskell.org/platform/mac.html

なので以下の手順でインストール

$ brew install ghc
~~
$ brew install cabal-install
~~
$ cabal update
~~
$ cabal install cabal-install
~~

何をインストールしているのか、どんな構造でHaskellを管理しているのかについては以下の記事が参考になる。
Haskellのパッケージ管理について調べてみた - りんごがでている

How to use

まずはインタラクティブなインターフェイスとコンパイルのコマンドから。

$ ghci
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 1 + 1
2
Prelude> 2 ^ 3
8
Prelude>:q
Leaving GHCi.

このようにしてHaskellに対してインタラクティブなインターフェイスを実行可能。

続いてコンパイル。以下のようなファイルを用意。

helloworld.hs

main = putStrLn "Hello World!"

以下ようにしてコンパイル

$ ghc helloworld.hs
[1 of 1] Compiling Main             ( helloworld.hs, helloworld.o )
Linking helloworld ...

実行ファイル他、ファイルが吐きだされるので実行

$ ./helloworld
Hello World!

とりあえず、こんな感じです。