AtCoder

ABC292 D問題(Unicyclic Components)を解く

AtCoder_ABC292_D

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

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

D問題 Unicyclic Components(Difficulty : 579)

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

ABC292 D問題 Unicyclic Components

グラフの連結成分が含む頂点と辺をカウントする問題です。AtCoder Problems による Difficulty は 579 でした。

解答案

与えらたグラフの連結成分に含まれる頂点の個数と辺の本数が等しいか調べます。連結成分については、ABC284 C問題でコードを紹介しました。

上記の基本的なコードに、各連結成分毎に頂点(vertex)と辺(edge)をカウントするコードを加えていきます。

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

初めて訪れる頂点で、頂点と辺の個数を増やします(15、16行目)。この変数は、連結成分毎にリセットしています(39、40行目)。辺の数は、グラフを登録するときに合わせて配列 n_of_edge に代入して、使っています(7、16、33行目)。

各連結成分毎に頂点と辺の数を確認しています(42-44行目)。

以下が、C++プログラムとなります。基本的なグラフのコードからの差分を背景色を変更しています。

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

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

int vertex;
int edge;

void dfs(int v)
{
	seen[v] = true;
	++vertex;
	edge += n_of_edge[v];
	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);
		++n_of_edge[u];
	}

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

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

	return 0;
}

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

Python プログラム例(ABC292D)

Python 版は、C++ 版を移植しました。再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています(5行目)。回数は余裕をみて設定しました。

"""AtCoder Beginner Contest 292 D"""
import sys

LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)


def dfs(v):
    global vertex, edge

    seen[v] = True
    vertex += 1
    edge += n_of_edge[v]
    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)
n_of_edge = [0] * (n + 1)

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

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

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

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

最後に

グラフの探索は、基本的にDFSを使っています。だいぶ慣れてきました。

ABC292 について、引き続き、E問題まで紹介します。

COMMENT

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

CAPTCHA