C++ の vectorの1次元配列を2次元配列として扱っていることについて

Question

前提・実現したいこと

Atcoderの競プロ典型90問の 003番の問題　
https://atcoder.jp/contests/typical90/tasks/typical90_c
の模範解答
https://github.com/E869120/kyopro_educational_90/blob/main/sol/003.cpp
についての質問です.
質問すべき場所を間違っていたら申し訳ありません.

ソースコード12行目では

vector<int> G[1 << 18];

と1次元配列として宣言されていますが, 39, 40行目では

		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);

と2次元配列に対する push_backを使用しています.

どうしてエラーが出ないんでしょうか?

該当のソースコード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 入力
int N;
int A[1 << 18], B[1 << 18];

// グラフ
const int INF = (1 << 29);
vector<int> G[1 << 18];
int dist[1 << 18];

void getdist(int start) {
	// 幅優先探索（BFS）により、最短距離を計算
	for (int i = 1; i <= N; i++) dist[i] = INF;

	queue<int> Q;
	Q.push(start);
	dist[start] = 0;

	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int to : G[pos]) {
			if (dist[to] == INF) {
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
}

int main() {
	// Step #1. 入力
	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i];
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}

	// Step #2. 頂点 1 からの最短距離を求める
	// maxid1: 頂点 1 から最も離れている（最短距離が長い）頂点
	getdist(1);
	int maxn1 = -1, maxid1 = -1;
	for (int i = 1; i <= N; i++) {
		if (maxn1 < dist[i]) {
			maxn1 = dist[i];
			maxid1 = i;
		}
	}

	// Step #3. 頂点 maxid1 からの最短距離を求める
	// maxn2: 木の直径（最短距離の最大値）
	getdist(maxid1);
	int maxn2 = -1;
	for (int i = 1; i <= N; i++) {
		maxn2 = max(maxn2, dist[i]);
	}

	// Step #4. 出力
	cout << maxn2 + 1 << endl;
	return 0;
}

試したこと

デバッグしてみても, Gは2次元配列となっていました.
G[2]の中に, G[2][0]や, G[2][1]があるわけですが, その容量は確保できていないように感じます.
vectorは可変長だから,

		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);

のような処理を行えば, 勝手に容量を逐一確保してくれているのでしょうか?

補足質問

const int INF = (1 << 29);

は, 距離distが計算されていないことを示すための値だと思いますが, どうして INFという変数名になっていると思いますか？

Answer 1

        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);

と2次元配列に対する push_backを使用しています.

A[i]やB[i]はint型ですので、例えばA[i]=0, B[i]=1とかだとすると

        G[0].push_back(1);
        G[1].push_back(0);

となります。

---

Gはvector<int>[]、つまりvector<int>の配列ですので、
G[A[i]]はvector<int>です。
vector<int>にint型のB[i]をpush_back()しているわけですから特に問題ありません

---

vector<int> G[1 << 18];

と1次元配列として宣言されていますが

なんかここから勘違いが始まっていそうなので一応解説すると
これはvector<int>が入る1<<18要素の配列であって
要素数を予め1<<18個確保したvector<int>ではありません。

(要するにこれ2次元です)

Comments

[jiltonB]

回答ありがとうございます.
例えば,
G[2].push_back(30) , G[2].push_back(40)
を行うと,
G[2][0]=30, G[2][1]=40 となるのでしょうか?

その場合, 最初に, G[2] = 1 と初期化されていた場合は, どうなるのでしょうか?

[ozwk]

> 例えば,
G[2].push_back(30) , G[2].push_back(40)
を行うと,
G[2][0]=30, G[2][1]=40 となるのでしょうか?

push_back()を行った時点でのG[2]の末尾に30，40が追加されます。

> G[2] = 1 と初期化されていた場合

G[2] はvector<int>型なので、1という初期化のされ方がありえません。

[jiltonB]

vectorを勘違いしていたようです.
例えば,
vector<int> a{1, 2, 3};
a.push_back(4)なら,
aが{1, 2, 3, 4}のようなイメージで,
a[0].push_back(4)
a[0].push_back(7) なら
aが
{1, 2, 3}で, a[0]に4, 7 というデータが紐づいているというイメージでしょうか?

のようなイメージなのでしょうか?

また先ほどのGの例で, 40のデータに参照しようと思ったら, どのように記述すればよいのでしょうか?
質問が多くてすみません. 答えていただけるとありがたいです.

[ozwk]

> 例えば,
vector<int> a{1, 2, 3};
a.push_back(4)なら,
aが{1, 2, 3, 4}のようなイメージで,

はい

> a[0].push_back(4) なら,
a[2].push_back(7)
aが{1, 2, 3}
4 7
のようなイメージなのでしょうか?

何言っているかわかりません。

[jiltonB]

すみません, 書き間違えていたようなので, 質問編集しました.

[ozwk]

> [0].push_back(4)
a[0].push_back(7) なら
aが
{1, 2, 3}で, a[0]に4, 7 というデータが紐づいているというイメージでしょうか?

いいえ、a[0]はint型なのでa[0].push_backの時点でコンパイルエラーです

[jiltonB]

ますますわからなくなってしまいました. バカですみません.
G[0].push_backとa[0].push_backには違いがないように感じます.

vector<int> a[100];
a[2].push_back(4);
a[2].push_back(7);

なら, aはどのようになっているのでしょうか

[ozwk]

a[2]のvector<int>に4,7が追加されます

[ozwk]

ひょっとしてこういう勘違いじゃないか?というのを回答に追記しておきました

[jiltonB]

vector<int> a = {1, 2, 3, 4 ,5}
は 要素数5の int の配列で,
vector<int> a[5]
は 要素数 5 の　vector<int> の配列ということでしょうか?

[ozwk]

はい
(前者はvectorを配列と言うのは違和感がありますが。)

[jiltonB]

いろいろとありがとうございました!

Answer 2

vector<int> G[1 << 18];

G は vector<int> を要素とする配列です。
G[A[i]] は vector<int> なので push_back() できます。

Comments

[jiltonB]

Gは int を要素とする配列で,
vector<vector<int>> G なら vector<int> を要素とする配列になるのではないでしょうか?

int を要素とするvectorの要素に対して push_back することで, その vector が vector<int> を要素とするようになるのかなと思いました.

[episteme]

> Gは int を要素とする配列で,

違います。 int を要素とする配列 なら int G[1<<18]; であるはず。

[jiltonB]

vectorについて理解が足りていなかったようでした. すみません.

vector<int> a(3); と
int a[3];
はどちらも同じ intを要素とする配列で,
vector<int> a[3] は
vector<int> を要素とする配列ということですね