AtCoder

ABC276 B問題(Adjacency List)を解く

AtCoder_ABC276_B

AtCoder が提供しているABC(AtCoder Beginner Contest)276 のB問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。

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

B問題 Adjacency List(Difficulty : 143)

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

ABC276 B問題 Adjacency List

グラフを読み込む問題です。AtCoder Problems による Difficulty は、143 でした。ABC B問題として、標準的な問題です。

解答案

問題を解く方針を書きだします。

  • n と m を読み込む。
  • m 個の辺(edge)を読み込み、頂点に登録する。
  • 各頂点に登録した頂点をソートする。
  • 頂点毎に隣接している頂点を表示する。

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

グラフを表現することは、ABC270 C問題でも紹介しました。そこで紹介したコードパターンを再掲します。

グラフの表現は、隣接リスト表現と呼ばれる、頂点 u から隣接している集合 vector e[u] を定義する方法がよく使われます。N 個の頂点と N – 1 個の辺を持つグラフの入力をするコードは以下となります。なおこの問題では向きを持たないため、両方向の登録をしています(10行目と11行目)。

vector<int> e[N];

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

	return 0;
}

CとC++の配列は、0からアクセスします(0オリジン)。このため、頂点に辺を登録する場合、頂点番号を1引いて登録します。解として表示するときは、1足して表示します。

このプログラムでは、一貫して、頂点番号を0からカウントしています。関連するコードの背景色を変更しました。

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> e[n];
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		e[u - 1].push_back(v - 1);
		e[v - 1].push_back(u - 1);
	}
	for (int i = 0; i < n; ++i) {
		cout << e[i].size();
		if (e[i].size() > 0) {
			sort(e[i].begin(), e[i].end());
			for (int j = 0; j < e[i].size(); ++j) {
				cout << " " << e[i][j] + 1;
			}
		}
		cout << endl;
	}

	return 0;
}

ただし、0オリジンは1個違いのミスをする可能性があります。このため、問題で与えられている1オリジンのまま処理するプログラムを紹介します。

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> e[n + 1];
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) {
		cout << e[i].size();
		if (e[i].size() > 0) {
			sort(e[i].begin(), e[i].end());
			for (int j = 0; j < e[i].size(); ++j) {
				cout << " " << e[i][j];
			}
		}
		cout << endl;
	}

	return 0;
}

差分の背景色を変更しました。1オリジンの場合、引いたり足したりすることがないため、ミスは少ないと思います。

ただし、各頂点と接続している頂点を表現する vector<int> の配列を n + 1 個確保する必要があります。これは、e[n] までアクセスするためです。また、e[0] は確保していますが、使いません。

グラフの処理は、問題の書き方に合わせるとミスが少なくなると思います。

Python プログラム例(ABC276B)

Python は、可読性を高くすることを意識して、1オリジンで記載しました。

"""AtCoder Beginner Contest 276 B"""
n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    e[u].append(v)
    e[v].append(u)
for i in range(1, n + 1):
    print(len(e[i]), end="")
    if len(e[i]) > 0:
        e[i].sort()
        print("", *e[i])
    else:
        print("")

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

最後に

グラフの辺を読み込み、接続している頂点を出力する基本的な問題です。

C++ では、0オリジンの場合と1オリジンの場合を紹介しました。アルゴリズムの教科書は無駄な領域がないため、0オリジンで書いてあることが多いです。一方、AtCoder の問題は、表現が自然に感じる1オリジンで書いてあることが多いです。

求められている場合に合わせることが重要だと考えています。

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

COMMENT

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

CAPTCHA