AtCoder

ABC287 C問題(Path Graph?)を解く

AtCoder_ABC287_C

AtCoder が提供しているABC(AtCoder Beginner Contest)287 のC問題をC++とPythonで解いてみました。ABC287は、2023年1月28日21:00に実施されました。

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

C問題 Path Graph?(Difficulty : 466)

問題はリンク先をご覧ください。

ABC287 C問題 Path Graph?

グラフが一本道の形になるか判定する問題です。AtCoder Problems による Difficulty は 466 でした。

解答案

問題文に、「単純無向グラフ」と「パスグラフ」の説明がありました。パスグラフについて、「グラフがひとつの線分の形になる」と解釈しました。

以下の条件を満たすグラフがパスグラフになります。これは、グラフの形をいくつか書いていくと分かりました。

  • 頂点の個数(N)に対して、辺の個数(M)は、N – 1 個となる。つまり N – 1 = M となる。
  • すべての頂点の次数は2以下となる。両端は次数1となり、残りが次数2となる。
  • 全体が連結している。

上2つの条件は、グラフとして入力されたデータから判断ができます。最後のひとつは、連結個数を求める問題となります。これは ABC284 C問題でも紹介しました。

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

方針に従い、プログラムしました。連結個数を求めるための探索には、慣れている DFS(深さ優先探索:Depth-First Search)を使いました。関数 dfs は、基本的な実装から変更していません。

パスグラフとなるかを Bool 型の変数 result で管理します。初期値を true にして、条件を満たさない場合に false にします。最終的に result に従い、”Yes” か “No” を出力します。

#include <bits/stdc++.h>
using namespace std;

#define N 200001
vector<vector<int>> e(N);
vector<bool> seen(N, false);

void dfs(int v)
{
	seen[v] = true;
	for (auto next_v : e[v]) {
		if (!seen[next_v]) {
			dfs(next_v);
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	bool result = true;

	if (n - 1 != m) {
		result = false;
	}

	for (int i = 1; i <= n; ++i) {
		if (e[i].size() > 2) {
			result = false;
		}
	}

	dfs(1);
	for (int i = 1; i <= n; ++i) {
		if (!seen[i]) {
			result = false;
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

Python プログラム例(ABC287C)

Python 版も、C++ プログラムを移植しました。グラフの表現と関数 dfs の実装は、ABC284 C問題を流用しました。また、再帰関数の呼び出し回数の上限を増やしています(2-5行目)。

"""AtCoder Beginner Contest 287 C"""
import sys

LIMIT = 2 * 10 ** 5 + 1
sys.setrecursionlimit(LIMIT)


def dfs(v):
    seen[v] = True
    for next_v in e[v]:
        if not seen[next_v]:
            dfs(next_v)


n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
seen = [False] * (n + 1)

for i in range(m):
    u, v = map(int, input().split())
    e[u].append(v)
    e[v].append(u)

result = True

if n - 1 != m:
    result = False

for i in range(1, n + 1):
    if len(e[i]) > 2:
        result = False

dfs(1)
for i in range(1, n + 1):
    if not seen[i]:
        result = False

print("Yes" if result else "No")

こちらも「AC」と判定されました。

最後に

パスグラフとなる条件を抽出することが難しい問題でした。

なお、コンテスト本番では、条件「すべての頂点の次数は2以下となる」が抜けていてもAC判定をもらうことができました。恥ずかしながら、わたくしの最初のプログラムもこの条件が抜けていました。

コンテスト後に、Twitter でこのことがコメントされて、すぐにテストケースが追加されていました。運営のみなさまの努力に感謝したいと思います。

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

COMMENT

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

CAPTCHA