ABC343 B問題（Adjacency Matrix）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）343 のB問題をC++とPythonで解いてみました。ABC343は、2024年3月2日21:00に実施されました。

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

B問題 Adjacency Matrix（Difficulty : 53）

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

ABC343 B問題 Adjacency Matrix

グラフの隣接行列から各頂点と接続している頂点を出力します。AtCoder Problems による Difficulty は 53 でした。

解答案

グラフの表現として、接続している辺が与えられる場合と、隣接行列が与えられる場合があります。

この問題では、隣接行列からそれぞれの頂点が直接接続している頂点を出力します。

C++ プログラム例（ABC343B）

行（頂点の情報）を読み、要素が1である列番号を出力します。プログラムは0からカウントしますが、問題は1からカウントした値を出力するため1を加えています。

以下が、C＋＋プログラムとなります。

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

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

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int a;
			cin >> a;
			if (a == 1) {
				cout << j + 1 << " ";
			}
		}
		cout << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC343B）

Python 版も基本的な考え方は同じです。各行の結果をリスト result に格納して、まとめて出力しています。以下となります。

"""AtCoder Beginner Contest 343 B"""
n = int(input())
for i in range(n):
    a = list(map(int, input().split()))
    result = []
    for j in range(n):
        if a[j] == 1:
            result.append(j + 1)
    print(*result)

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

最後に

AtCoder では、グラフの隣接行列の表現はあまりでてこない気がします。これは頂点数が多いグラフの入力が大きくなるからだと考えています。この問題で、隣接行列について学べました。

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