問題一覧 > 教育的問題

No.2910 単体ホモロジー入門

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : 👑 p-adicp-adic / テスター : TakaTaka
0 ProblemId : 9083 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-08 11:54:48

問題文

入力に正整数 NN と非負整数 MM と、NN 未満の各非負整数を頂点とする(自己ループや多重辺を持たない)NN 頂点 MM 辺の無向グラフ GG と、33 個の NN 未満の非負整数 v0,v1,v2v_0, v_1, v_2 が与えられます。

 

GG の閉路であってそれが通る頂点全体の集合が {v0,v1,v2}\{v_0, v_1, v_2\}一致しないものが存在するか否かを判定してください。

 

ただしここで GG の閉路とは、大雑把には GG の辺を辿って頂点を移動する経路であって、始端と終端のみが等しく、それ以外は全ての異なる点を通るもののことです。

閉路の厳密な定義が知りたい人向けの説明はこちらです。(クリックで開く)

 

GG の閉路とは、GG の辺からなる長さ 11 以上の有限列 ee であって、その長さを \ell と置き \ell 未満の各非負整数 jj に対し ee1+j1+j 個目の成分を eje_j と置いた時に以下の 22 条件を満たすもののことです:

  • 0j0<j1<0 \leq j_0 < j_1 < \ell を満たす任意の整数 j0,j1j_0,j_1 に対し、ej0ej1e_{j_0} \neq e_{j_1} である。
  • GG の頂点からなる長さ +1\ell + 1 の列 cc であって、\ell 以下の各非負整数 ii に対し cc1+i1+i 個目の成分を cic_i と置いた時に以下の 22 条件を満たすものが存在する:
    • 0j<0 \leq j < \ell を満たす任意の整数 jj に対し、eje_jcjc_jcj+1c_{j+1} を結ぶ GG の辺である。
    • 0i0<i10 \leq i_0 < i_1 \leq \ell を満たす任意の整数 i0,i1i_0,i_1 に対し、(i0,i1)=(0,)(i_0,i_1) = (0,\ell)ci0=ci1c_{i_0} = c_{i_1} は同値である。

また上の記法において ee が通る頂点とは GG の頂点 vv であって vveje_j の端点であるような \ell 未満の非負整数 jj が存在するもののことです。

背景

単体複体と呼ばれる幾何的データには単体ホモロジーという次数付きの不変量が定義されます。単体ホモロジーは各次数ごとに可換群と呼ばれる代数構造などが付与されたデータで、各非負整数 dd に対し dd 次のデータは dd 次単体ホモロジー群と呼ばれます。

この問題は GG から構成される 11 次元単体複体に {v0,v1,v2}\{v_0,v_1,v_2\} に対応する面を貼り付けて得られる 22 次元単体複体の 11 次単体ホモロジー群が自明群であるという性質を満たすか否かを判定する問題と密接に関わります。ただし 11 次単体ホモロジー群を計算する問題では {v0,v1,v2}\{v_0,v_1,v_2\} の部分集合 {v0,v1},{v0,v2},{v1,v2}\{v_0,v_1\}, \{v_0,v_2\}, \{v_1,v_2\} に対応する辺たちが全て GG の辺である必要がありますが、この問題自体にはそのような制約が必要ないので課していません。

入力

GG の辺を MM 未満の各非負整数 mm で番号付けて辺 mm と呼びます。MM 未満の各非負整数 mm に対し、辺 mm の端点を imi_mjmj_mim,jmi_m,j_mim<jmi_m < j_m を満たす NN 未満の非負整数)と置きます。

この時、入力は以下の形式で標準入力から 2+M2 + M 行で与えられます:

  • 11 行目に N,MN, M が半角空白区切りで与えられます。
  • MM 未満の各非負整数 mm に対し、2+m2 + m 行目に im,jmi_m, j_m が半角空白区切りで与えられます。
  • 2+M2 + M 行目に v0,v1,v2v_0, v_1, v_2 が半角空白区切りで与えられます。
NN MM
i0i_0 j0j_0
\vdots
iM1i_{M-1} jM1j_{M-1}
v0v_0 v1v_1 v2v_2

制約

入力は以下の制約を満たします:

  • NN1N41 \leq N \leq 4 を満たす整数である。
  • MM0M12N(N1)0 \leq M \leq \frac{1}{2}N(N-1) を満たす整数である。
  • MM 未満の任意の非負整数 mm に対し、imi_mjmj_m0im<jm<N0 \leq i_m < j_m < N を満たす整数である。
  • MM 未満の任意の非負整数 m0,m1m_0,m_1 に対し、m0m1m_0 \neq m_1 ならば (im0,jm0)(im1,jm1)(i_{m_0},j_{m_0}) \neq (i_{m_1},j_{m_1}) である。
  • v0v_00v0<N0 \leq v_0 < N を満たす整数である。
  • v1v_10v1<N0 \leq v_1 < N を満たす整数である。
  • v2v_20v2<N0 \leq v_2 < N を満たす整数である。

出力

GG の閉路であってそれが通る頂点全体の集合が {v0,v1,v2}\{v_0, v_1, v_2\}一致しないものが存在する場合はYesと、存在しない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
0 1
0 2
1 2
0 0 0

このように v0,v1,v2v_0, v_1, v_2 が 重複することもあります。

出力
Yes

「辺 00、辺 22、辺 11」と辿る経路は閉路をなし、それが通る頂点全体の集合は {0,1,2}\{0,1,2\} であって {v0,v1,v2}={0,0,0}={0}\{v_0,v_1,v_2\} = \{0,0,0\} = \{0\} とは一致しません。

サンプル2
入力
3 3
0 1
0 2
1 2
2 0 1

このように v0,v1,v2v_0, v_1, v_2 が 昇順でないこともあります。

出力
No

「辺 00、辺 22、辺 11」と辿る経路は閉路をなしますが、それが通る頂点全体の集合 {0,1,2}\{0,1,2\}{v0,v1,v2}={2,0,1}\{v_0,v_1,v_2\} = \{2,0,1\} と一致してしまいます。他の閉路も同様です。

サンプル3
入力
4 4
0 1
0 3
1 2
2 3
0 1 2

このように {v0,v1,v2}\{v_0, v_1, v_2\} の部分集合 {v0,v1},{v0,v2},{v1,v2}\{v_0,v_1\}, \{v_0,v_2\}, \{v_1,v_2\} に対応する辺たちを GG が持たないこともあります。今回は {v0,v2}={0,2}\{v_0,v_2\} = \{0,2\} に対応する辺が GG にはありません。

出力
Yes

「辺 00、辺 22、辺 33、辺 11」と辿る経路は閉路をなし、それが通る頂点全体の集合は {0,1,2,3}\{0,1,2,3\} であって {v0,v1,v2}={0,1,2}\{v_0,v_1,v_2\} = \{0,1,2\} とは一致しません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。