AtCoder

ABC075 C問題(Bridge)を解く

AtCoder_ABC075_C

AtCoder が提供しているABC(AtCoder Beginner Contest)075 C問題をC++で解いてみました。ABC075は、2017年10月14日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Bridge(Difficulty : 1067)

問題の詳細は、リンク先をご覧ください。

ABC075 C問題 Bridge

特定の辺を取り除いたときに、グラフが連結しているかを調べます。AtCoder Problems による Difficulty は 1067 でした。

解答案

辺をひとつずつ抜いて、グラフが連結しているか調べます。連結でなければその辺は橋です。グラフが連結しているかは、BFS(幅優先探索:Breadth-First search)、DFS(深さ優先探索:Depth-First Search)、UnionFind を用いて調べることができます。

C++ プログラム例(ABC075C)

BFS(幅優先探索:Breadth-First search)で調べる。

最初に BFS で調べたプログラムを紹介します。

  • 特定の辺を抜いてグラフ $G$ を定義します(19ー26行目)。
  • キューを用いて頂点 $0$ からの最短距離を求めます(28ー41行目)。
  • 最短距離が-1の頂点が存在する場合、グラフは連結していません(43ー48行目)。
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> a(m);
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	int result = 0;
	for (int i = 0; i < m; ++i) {
		vector<vector<int>> G(n);
		for (int j = 0; j < m; ++j) {
			if (i == j) {
				continue;
			}
			G[a[j]].push_back(b[j]);
			G[b[j]].push_back(a[j]);
		}

		vector<int> dist(n, -1);
		queue<int> que;
		que.push(0);
		dist[0] = 0;
		while (!que.empty()) {
			int now = que.front();
			que.pop();
			for (auto next_v : G[now]) {
				if (dist[next_v] == -1) {
					que.push(next_v);
					dist[next_v] = dist[now] + 1;
				}
			}
		}

		for (int j = 0; j < n; ++j) {
			if (dist[j] == -1) {
				++result;
				break;
			}
		}
	}

	cout << result << endl;

	return 0;
}

DFS(深さ優先探索:Depth-First Search)で調べる。

次に DFS で調べたプログラムを紹介します。BFS との差分は以下です。

  • ラムダ式を用いて再帰で連結している頂点を求めます(28ー37行目)。
  • 訪れていない頂点があれば、グラフは連結していません(39ー44行目)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> a(m);
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	int result = 0;
	for (int i = 0; i < m; ++i) {
		vector<vector<int>> G(n);
		for (int j = 0; j < m; ++j) {
			if (i == j) {
				continue;
			}
			G[a[j]].push_back(b[j]);
			G[b[j]].push_back(a[j]);
		}

		vector<bool> seen(n, false);
		auto dfs = [&](auto self, int v) -> void {
			seen[v] = true;
			for (auto next_v : G[v]) {
				if (!seen[next_v]) {
					self(self, next_v);
				}
			}
		};
		dfs(dfs, 0);

		for (int j = 0; j < n; ++j) {
			if (!seen[j]) {
				++result;
				break;
			}
		}
	}

	cout << result << endl;

	return 0;
}

UnionFind で調べる。

最後にUnionFind で調べたプログラムを紹介します。一番簡潔に書けています。UnionFind の実装は、ACL(AtCorder Library)をを使用しました。

  • 特定の辺を抜いて UnionFind 木に merge していきます(21ー26行目)。
  • 特定の辺が同じ UnionFind 木に属していなければ連結していません(28ー30行目)
#include <atcoder/dsu>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> a(m);
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	int result = 0;
	for (int i = 0; i < m; ++i) {
		dsu uf(n);
		for (int j = 0; j < m; ++j) {
			if (i != j) {
				uf.merge(a[j], b[j]);
			}
		}

		if (!uf.same(a[i], b[i])) {
			++result;
		}
	}

	cout << result << endl;

	return 0;
}

すべて AC(Accepted=正しいプログラム)と判定されました。

最後に

グラフの連結について、3つの異なるアルゴリズムを使って調べました。勉強になりました。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA