グラフを作成し、深さ優先検索を行う次のコードを見ました。ベクトル g の使い方を教えてください。2番目の関数では、2次元のものとしてどのように記述されていますか。この目的でベクターを使用することについて、全体のプロセスを明確に説明してください。問題は次のとおりです:--- ある企業が、1 から n までの番号が付けられた n 都市に接続されています。現在、会社の本社はインデックス hq1 に位置しています。接続された都市の各ペアは、双方向で接続されています。接続は、本社から各都市への接続が 1 つだけ存在するようなものです。接続された都市のマップは、次のように保持されます。本社とは異なる各都市 i について、番号 ci が保持されます。これは、本社から i に向かう途中の最後の都市のインデックスです。
その会社は、本社を市 hq1 から市 hq2 に移転することを決定しました。そのため、この変更後、上記の地図の古い表現は正しくなくなりました。上記の方法で会社が新しい地図を見つけるのを手伝ってください.
入力
最初の行には、テスト ケースの数が含まれています (0 < T <= 10 )。次の行には、スペースで区切られた 3 つの整数 n、hq1、hq2 (2 ≤ n ≤ 2*10^4、1 ≤ hq1 ≠ hq2 ≤ n) が含まれます — 接続された都市の数、古い本社のインデックス、および新しい本社のインデックス、 それぞれ。
次の行には、スペースで区切られた n - 1 個の整数が含まれています — マップの古い表現です。hq1 以外の各都市には、整数 ci が与えられます。これは、本社から都市 i に向かう途中の最後の都市のインデックスです。すべての都市は、インデックスの昇順で記述されています。
出力
n - 1 の数値を出力 — 同じ形式でのマップの新しい表現。解決策を以下に示します。
vector < int >g[10005];
void make_graph()
{
int k = 1;
for (int i = 1; i <= n; i++)
{
if (i == h1)
continue;
int x;
cin >> x;
g[x].push_back (i);
g[i].push_back (x);
}
}
int visited[20004], parent[20004];
void dfs(int x)
{
visited[x] = 1;
for (int i = 0; i < g[x].size (); i++)
{
int j = g[x][i];
if (j == parent[x])
continue;
parent[j] = x;
dfs (j);
}
return;
}
int
main ()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> h1 >> h2;
make_graph ();
dfs (h2);
for (int i = 1; i < n; i++)
{
if (i == h2)
continue;
cout << parent[i] << " ";
}
if (n != h2)
cout << parent[n] << endl;
else
cout << endl;
memset (parent, 0, sizeof (parent));
memset (visited, 0, sizeof (parent));
for (int i = 1; i <= n; i++)
g[i].clear ();
}
return 0;
}