[AOJ] No. 0321 部活動調査

問題

方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所属しているという情報から、

\[ g_a \neq g_b \wedge g_a \neq 0 \wedge g_b \neq 0\]

のとき校則に違反していることになります。また、\( g_a \neq 0\) または \( g_b \neq 0 \) のとき、生徒 \( a, b \) の隣接リストを走査して校則に違反しているかどうかを調べます。これは、幅優先探索を行うことで実現できます。

つぎに、生徒 \( c \) が部活動 \( x \) に所属しているという情報から、生徒 \( c \) の隣接リストを走査します。

コード