中央大学 理工学研究科 情報工学専攻 2026年2月実施 一般入試（春季）問題II

标签：

• 中央大学
• 并查集
• 并查集的路径压缩

Author

祭音Myyura (Based on 中央大学の公式解答例 refined with GPT 6 Astra)

Description

問題 I は必答。問題 II～V のうち、2 問を選んで解答すること。

問題 II. つぎの設問に答えよ。

1. 画面に表示される $n$ 枚の色つき板 (panel) を考える $(1\leq n<10^5)$。板は番号 $k$ $(0\leq k<n)$ で指定され、その色は色番号 $C_k$ $(0\leq C_k<n)$ で示される。ここで、板 $i$ と $j$ $(0\leq i,j<n)$ について、板 $j$ の色番号 $C_j$ と同じ色番号を持つすべての板の色番号を、$C_i$ に上書きする操作を「$\operatorname{set\_color}(i,j)$」と記す。初期状態では $C_k=k$ $(0\leq k<n)$ とし、$m$ 個の操作を順次施し、各板の色番号を計算する。色は複数回上書きされ得る。

1: #include<stdio.h>
2: int n; int c[100000];
3: int get_color(int i){ return c[i];} /* 板 i の色番号を返す関数 */
4: void set_color(int i,int j){int cj=c[j],k; for(k=0;k<n;k++)if(c[k]==cj)c[k]=c[i];}
5: void put_color(){for(int i=0;i<n;i++)printf("%d%c",get_color(i),i<(n-1)?' ':'\n');}
6: int main(){ int m;
7:   scanf("%d %d",&n,&m); /* n: 板数, m: 指示数 */
8:   for(int k=0;k<n;k++) c[k]=k;
9:   for(int k=0;k<m;k++){int i,j; scanf("%d %d",&i,&j); set_color(i,j); put_color();}
10: }

図 1　プログラム P1。$C_k$ の値を配列要素 c[k] に計算する。（紙面の都合上エラー処理等は省略して記載。）

図 2　初期状態（左）と最終状態（右）。数値は色番号を表す。（色をパターンで示した。）

上記 P1 は $C_k$ を計算するプログラムの例である。まず、データの先頭行から $n$ と $m$ の値を読んで、続いて $m$ 行の各行に記された 2 個の整数「$i$　$j$」を読み込み、各行が表す「$\operatorname{set\_color}(i,j)$」という操作を順番に施す。

例えば、1 行に整数を 2 個ずつ「6　3」、「4　1」、「2　3」、「4　3」として、全 4 行をこの順に与えた場合を考える。入力の先頭行から $n=6,m=3$ が設定され、P1 の 8 行目で配列 c[] の先頭 6 個の要素が $\{0,1,2,3,4,5\}$ に初期化される。set_color 操作を表すデータは $3(=m)$ 行あり、次の行「4　1」が 1 番目の操作「set_color(4,1)」を表し、その結果として「0 4 2 3 4 5」が出力され、「2　3」が 2 番目の操作を表して結果が「0 4 2 2 4 5」、「4　3」が 3 番目の操作を表して結果が「0 4 4 4 4 5」と表示される（図 2）。

以下の設問 (1)、(2) に答えよ。

(1) このプログラム P1 を実行し、入力として各行に 2 個の整数を、順番に「8　5」、「5　3」、「2　4」、「6　0」、「4　5」、「7　3」として、全 6 行を与えたときの出力を記せ。

(2) 上記 P1 では、配列「int c[100000];」に色番号を格納している。プログラム P1 の 3～4 行目に基づき、関数 get_color() と set_color() の計算方法を説明し、正しい結果が得られることを説明せよ。

2. 図 1 のプログラム P1 中の配列 c[i] の値が表す意味を変更し、板 $i$ の色番号と同じ色番号を持つ板の番号（のひとつ）を表すこととする。次の方針により、上記と異なるアルゴリズムを構成できる。

（方針 1）初期状態では、番号 $k$ の板は色番号 $k$ の代表板であり、c[k] の値は $k$ である。

（方針 2）ある板 $i$ の代表板の色番号は、c[i] の値を $j$ として、$j=i$ なら $i$ である。そうでなければ、板 $j$ の代表板の色番号に等しい。c[i] の値をその代表板の番号（色番号と等しい）に更新する。

（方針 3）色の上書き指示「$\operatorname{set\_color}(i,j)$」の処理は、上書きされる板 $j$ の代表板の色番号を、上書きする板 $i$ の代表板の色番号にする。

以下の設問 (1)、(2) に答えよ。

(1) 上記 P1 の 3 行目の「int get_color(int i){...}」を再帰関数として再定義せよ。それに合わせて、4 行目の「void set_color(int i,int j){...}」を再定義せよ。各定義は 3 行以下で記述し、処理の長所・短所について P1 と比較し説明せよ。この修正版を P2 と記す。（エラー処理等の記述は不要。）

(2) (1) の修正版 P2 に、問題 1(1) と同じ 6 行の入力を与えたときの出力を記し、その動作を説明せよ。

题目描述

问题 I 为必答题；从问题 II～V 中选择 2 题作答。

问题 II：回答下列问题。

1. 考虑画面中的 $n$ 块彩色板（panel），其中 $1\leq n<10^5$。板以编号 $k$（$0\leq k<n$）指定，其颜色由色号 $C_k$（$0\leq C_k<n$）表示。对于板 $i,j$（$0\leq i,j<n$），将所有与板 $j$ 具有相同色号 $C_j$ 的板统一改为色号 $C_i$，记这一操作为 $\operatorname{set\_color}(i,j)$。初始状态为 $C_k=k$（$0\leq k<n$）。依次进行 $m$ 个操作，计算每块板的色号；同一颜色可能被多次覆盖。

图 1 的程序 P1 见上方代码：色号 $C_k$ 保存在数组元素 c[k] 中；第 3 行的 get_color(i) 返回板 $i$ 的色号，第 7 行读入板数 $n$ 和操作数 $m$。其余代码、行号及格式与原文相同，错误处理等因篇幅省略。图 2 左侧为初始状态，右侧为最终状态，数字表示色号，纹理表示颜色。

P1 首先从输入首行读取 $n,m$，然后读取后续 $m$ 行中的两个整数 $i,j$，依次执行各行对应的 $\operatorname{set\_color}(i,j)$。

例如，输入依次为「6　3」「4　1」「2　3」「4　3」，每行两个整数，共 4 行。首行设定 $n=6,m=3$，第 8 行把 c[] 的前 6 项初始化为 $\{0,1,2,3,4,5\}$。后续 $3(=m)$ 行指定操作：「4　1」表示第一个操作 set_color(4,1)，输出「0 4 2 3 4 5」；「2　3」指定第二个操作，输出「0 4 2 2 4 5」；「4　3」指定第三个操作，输出「0 4 4 4 4 5」（图 2）。

(1) 执行 P1，依次输入「8　5」「5　3」「2　4」「6　0」「4　5」「7　3」，每行两个整数，共 6 行。写出输出。

(2) P1 用数组 int c[100000]; 保存色号。根据第 3～4 行，说明 get_color() 和 set_color() 的计算方法，并解释为何能够得到正确结果。

2. 改变 P1 中 c[i] 的含义，使其保存一块与板 $i$ 具有相同色号的板的编号。按以下方针构造另一种算法。

方针 1：初始时，编号为 $k$ 的板是色号 $k$ 的代表板，c[k]=k。

方针 2：令 $j=$ c[i]。若 $j=i$，则板 $i$ 的代表板色号为 $i$；否则，它等于板 $j$ 的代表板色号。将 c[i] 更新为该代表板的编号（也等于色号）。

方针 3：执行覆盖操作 $\operatorname{set\_color}(i,j)$ 时，将被覆盖的板 $j$ 的代表板色号设为覆盖它的板 $i$ 的代表板色号。

(1) 把 P1 第 3 行的 int get_color(int i){...} 重新定义为递归函数，并相应重新定义第 4 行的 void set_color(int i,int j){...}。每个函数定义不超过 3 行。与 P1 比较，说明处理方法的优缺点。将修改后的程序称为 P2；无需写错误处理。

(2) 向 P2 输入与问题 1(1) 相同的 6 行输入，写出输出，并说明运行过程。

Kai

1(1) 出力

0 1 2 5 4 5 6 7
0 1 2 5 2 5 6 7
6 1 2 5 2 5 6 7
6 1 2 2 2 2 6 7
6 1 7 7 7 7 6 7

各操作で変更される板の集合は、順に $\{3\}$、$\{4\}$、$\{0\}$、$\{3,5\}$、$\{2,3,4,5\}$ である。

1(2) 正当性

get_color(i) は、配列に保存された現在の色番号 c[i] をそのまま返す。

set_color(i,j) は、操作前の色番号 c[j] を cj に保存し、全ての板を走査して c[k]==cj の要素だけを c[i] に変更する。cj を保存しておけば、途中で c[j] 自身が変更されても、操作前の同色集合を最後まで正しく判定できる。

また、操作前の c[i] と cj が異なれば板 $i$ は変更対象ではなく、走査中の c[i] は不変である。両者が等しければ同じ色で上書きするだけなので、やはり c[i] は変わらない。従って、変更対象の全てを操作前の $C_i$ に更新し、それ以外を変更しない。

初期化は $C_k=k$ を満たし、各操作が上の規則を保つため、任意の操作列について正しい色番号が得られる。

2(1) 再帰と経路圧縮

各関数を次のように定義できる。

int get_color(int i){
    return c[i]==i ? i : (c[i]=get_color(c[i]));
}

void set_color(int i,int j){
    int ri=get_color(i), rj=get_color(j); c[rj]=ri;
}

c[i] を親へのポインタとみなすと、各色の集合は根を代表板とする木になる。get_color は根まで再帰して根の番号を返し、その途中の各要素を根に直接つなぐ（経路圧縮）。set_color は板 $j$ の属する木の根を板 $i$ の属する木の根につなぐ。同じ木なら根を自分自身に設定するだけなので、循環は生じない。

P1 は get_color が $O(1)$、set_color が $\Theta(n)$ である。P2 は根の更新自体が $O(1)$ であり、集合全体を走査せずに色を統合できる。経路圧縮により、再度同じ経路を探索するときの手間も減る。一方、圧縮前には高さ $O(n)$ の木が生じ得るため、1 回の探索・更新の最悪時間は $O(n)$ で、再帰スタックも最悪 $O(n)$ 必要になる。順位・サイズによる併合は行っていないため、その併用を前提とする逆アッカーマン関数の計算量評価をそのまま適用してはならない。

なお、このプログラムでは毎回 put_color() が全 $n$ 枚を出力するので、1 操作当たり少なくとも $\Omega(n)$ の出力時間が必要である。

2(2) 出力と動作

出力は 1(1) と同じである。

0 1 2 5 4 5 6 7
0 1 2 5 2 5 6 7
6 1 2 5 2 5 6 7
6 1 2 2 2 2 6 7
6 1 7 7 7 7 6 7

代表板の併合は次の順で起こる。

操作	根の更新	新しい同色集合
set_color(5,3)	$3\to5$	$\{3,5\}$、色 $5$
set_color(2,4)	$4\to2$	$\{2,4\}$、色 $2$
set_color(6,0)	$0\to6$	$\{0,6\}$、色 $6$
set_color(4,5)	$5\to2$	$\{2,3,4,5\}$、色 $2$
set_color(7,3)	$2\to7$	$\{2,3,4,5,7\}$、色 $7$

配列には途中で親の番号が残ることがあるが、put_color() は c[i] を直接出力せず、各板に対して get_color(i) を呼ぶ。このため、必ず根の番号、すなわち現在の色番号が出力され、同時に経路が圧縮される。

Reference

• 中央大学公式問題（2026年度、冊子 p.16／PDF 第17頁；選答方法：冊子 p.14）
• 中央大学公式解答例・出題の意図（2026年度、冊子 p.20／PDF 第21頁）