問題一覧 >
教育的問題
No.2910 単体ホモロジー入門
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 48
作問者 : 👑
p-adic
/ テスター :
Taka
問題文最終更新日: 2024-02-08 11:54:48
問題文
入力に正整数 N と非負整数 M と、N 未満の各非負整数を頂点とする(自己ループや多重辺を持たない)N 頂点 M 辺の無向グラフ G と、3 個の N 未満の非負整数 v0,v1,v2 が与えられます。
G の閉路であってそれが通る頂点全体の集合が {v0,v1,v2} と一致しないものが存在するか否かを判定してください。
ただしここで G の閉路とは、大雑把には G の辺を辿って頂点を移動する経路であって、始端と終端のみが等しく、それ以外は全ての異なる点を通るもののことです。
閉路の厳密な定義が知りたい人向けの説明はこちらです。(クリックで開く)
G の閉路とは、G の辺からなる長さ 1 以上の有限列 e であって、その長さを ℓ と置き ℓ 未満の各非負整数 j に対し e の 1+j 個目の成分を ej と置いた時に以下の 2 条件を満たすもののことです:
- 0≤j0<j1<ℓ を満たす任意の整数 j0,j1 に対し、ej0=ej1 である。
- G の頂点からなる長さ ℓ+1 の列 c であって、ℓ 以下の各非負整数 i に対し c の 1+i 個目の成分を ci と置いた時に以下の 2 条件を満たすものが存在する:
- 0≤j<ℓ を満たす任意の整数 j に対し、ej は cjと cj+1 を結ぶ G の辺である。
- 0≤i0<i1≤ℓ を満たす任意の整数 i0,i1 に対し、(i0,i1)=(0,ℓ) と ci0=ci1 は同値である。
また上の記法において e が通る頂点とは G の頂点 v であって v が ej の端点であるような ℓ 未満の非負整数 j が存在するもののことです。
背景
単体複体と呼ばれる幾何的データには単体ホモロジーという次数付きの不変量が定義されます。単体ホモロジーは各次数ごとに可換群と呼ばれる代数構造などが付与されたデータで、各非負整数 d に対し d 次のデータは d 次単体ホモロジー群と呼ばれます。
この問題は G から構成される 1 次元単体複体に {v0,v1,v2} に対応する面を貼り付けて得られる 2 次元単体複体の 1 次単体ホモロジー群が自明群であるという性質を満たすか否かを判定する問題と密接に関わります。ただし 1 次単体ホモロジー群を計算する問題では {v0,v1,v2} の部分集合 {v0,v1},{v0,v2},{v1,v2} に対応する辺たちが全て G の辺である必要がありますが、この問題自体にはそのような制約が必要ないので課していません。
入力
G の辺を M 未満の各非負整数 m で番号付けて辺 m と呼びます。M 未満の各非負整数 m に対し、辺 m の端点を im と jm (im,jm はim<jm を満たす N 未満の非負整数)と置きます。
この時、入力は以下の形式で標準入力から 2+M 行で与えられます:
- 1 行目に N,M が半角空白区切りで与えられます。
- M 未満の各非負整数 m に対し、2+m 行目に im,jm が半角空白区切りで与えられます。
- 2+M 行目に v0,v1,v2 が半角空白区切りで与えられます。
N M
i0 j0
⋮
iM−1 jM−1
v0 v1 v2
制約
入力は以下の制約を満たします:
- N は 1≤N≤4 を満たす整数である。
- M は 0≤M≤21N(N−1) を満たす整数である。
- M 未満の任意の非負整数 m に対し、im と jm は 0≤im<jm<N を満たす整数である。
- M 未満の任意の非負整数 m0,m1 に対し、m0=m1 ならば (im0,jm0)=(im1,jm1) である。
- v0 は 0≤v0<N を満たす整数である。
- v1 は 0≤v1<N を満たす整数である。
- v2 は 0≤v2<N を満たす整数である。
出力
G の閉路であってそれが通る頂点全体の集合が {v0,v1,v2} と一致しないものが存在する場合はYes
と、存在しない場合はNo
と出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3
0 1
0 2
1 2
0 0 0
このように v0,v1,v2 が 重複することもあります。
出力
Yes
「辺 0、辺 2、辺 1」と辿る経路は閉路をなし、それが通る頂点全体の集合は {0,1,2} であって {v0,v1,v2}={0,0,0}={0} とは一致しません。
サンプル2
入力
3 3
0 1
0 2
1 2
2 0 1
このように v0,v1,v2 が 昇順でないこともあります。
出力
No
「辺 0、辺 2、辺 1」と辿る経路は閉路をなしますが、それが通る頂点全体の集合 {0,1,2} は {v0,v1,v2}={2,0,1} と一致してしまいます。他の閉路も同様です。
サンプル3
入力
4 4
0 1
0 3
1 2
2 3
0 1 2
このように {v0,v1,v2} の部分集合 {v0,v1},{v0,v2},{v1,v2} に対応する辺たちを G が持たないこともあります。今回は {v0,v2}={0,2} に対応する辺が G にはありません。
出力
Yes
「辺 0、辺 2、辺 3、辺 1」と辿る経路は閉路をなし、それが通る頂点全体の集合は {0,1,2,3} であって {v0,v1,v2}={0,1,2} とは一致しません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。