グラフDFS問題編 その３ (ABC075-C)

まだまだ続くよグラフDFS第三回。早速問題に入っていきましょう

今回の問題

C - Bridge
C問題なのに難易度がD問題相当に見えるのは気のせいでしょうか。次から解説です。

解説

1、入力について考える

今までは距離について扱っていましたが、今回は連結のみ。そして辺を消すといった動作が加わっています。この部分を上手く済ませることが出来れば簡単になりそうです。
辺を消すといった動作の場合、隣接リストだと毎回格納しているリストを参照する必要があり、少々大変です。
また、連結判定はbool値を用いるため、メモリ消費量が抑えられる可能性が高いです。さらにグラフのサイズも小さいため、今回は隣接行列を用います。

いつも通り入力から入ります。

#include <iostream>
#include <vector>

using namespace std;

int N;//隣接行列の場合は頂点数はグローバルに置いた方が楽なことが多い
int a[60], b[60];

bool G[60][60];
bool vis[60];


int main() {
    int M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の作成
    }//グラフ作成完了

}

代入演算子は右結合のため、上記のような書き方が出来るようです。

2、処理の実装

今回の問題は操作どうりに動かすことが可能です。すなわち、

１、一つ辺を消す。
２、頂点0からのDFSで全ての頂点を訪れることが出来るか試す。
３、全ての頂点に訪れているかvisited配列をforループで確認。訪れていない場合はカウントする。
４、消した辺を復元する。

以上のことを全ての辺にやってあげることで解けます。こういった全探索の場合は一回目の処理を適当にでもいいので書くと書きやすい気がします。

今回もコードに解説がてんこ盛りなのでそちらをご覧ください

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int a[60], b[60];

bool G[60][60];
bool vis[60];

void dfs(int v) {
    vis[v] = true;
    for (int i = 0; i < N; ++i) {
        if (G[v][i] == false) continue;//今回はNが小さいので遠慮しない
        if (vis[i] == true) continue;//既に訪れている 
        dfs(i);
    }
}

int main() {
    int M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の作成
    }//グラフ作成完了

    int cou = 0;//橋の個数
    for (int i = 0; i < M; ++i) {
        G[a[i]][b[i]] = G[b[i]][a[i]] = false;//辺の消去
        fill(vis, vis + N, false);//連結判定のため初期化

        dfs(0);//頂点0から訪れることが出来ないということは非連結

        bool no_connect = false;//辺であるか否か
        for (int j = 0; j < N; ++j) {//N個の頂点全てに訪れているはず
            if (vis[j] == false) no_connect = true;
        }
        if (no_connect) cou++;

        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の復元
    }

    cout << cou << endl;
}

こうしてみるとNが小さい場合は隣接行列の方が使い勝手がいいですね。自分ももっと使うことにします。今回はここまで。

ということでまさかの第三回まで続きました。ここまで来たらatcoderでDFSで解けそうなグラフ問題は全て記事にしていきたいです。おしまい。
6/22追記:まだDFSで解ける問題はあると思っていたのですが、なんとABC100回までには300点や400点にDFSが使いやすい問題はもうありませんでした。よって次回はまとめです。