No.3029 オイラー標数
タグ : / 解いたユーザー数 61
作問者 :

問題文
三つの正整数からなるクエリ が与えられます()。ただし です。
集合 を全てはじめ空集合にしておき、クエリ に対して、次の操作を行います。
- 3つの整数 を に追加する。
- 3つの2元集合 を に追加する。
- 3元集合 を に追加する。
有限集合 の要素数を と表すことにして、 個のクエリを処理したあとの について を出力してください。
背景
幾何学では三次元の多面体について、点の数、辺の数、面の数をそれぞれ としたとき をオイラー標数と言います。これは多面体の「穴の個数」と関わりがあり、現代の位相幾何学の入口にある不変量です。
入力から作られる はそれぞれ多面体の点、辺、面(三角形)を集めたものと解釈できます。
このように、図形の点や辺、面の繋がり方だけを抽出したデータを「抽象単体複体」と言います。
入力
出力
最後に改行してください。
サンプル
サンプル1
入力
4 1 2 3 1 2 4 1 3 4 2 3 4
出力
2
したがって、 が出力されます。
この入力は四面体の各面を構成する頂点たちからなるクエリです。
サンプル2
入力
14 1 2 4 5 6 7 4 6 7 1 5 6 2 3 7 1 3 7 2 4 5 2 5 7 1 4 7 1 2 6 2 3 6 3 4 6 3 4 5 1 3 5
出力
0
これはトーラスという曲面の三角形分割を意図したクエリになっています。
この図では という頂点や という辺などが複数個存在しますが、本来は一つしかなく(貼り合わせる)、二次元平面内で図示するためにあえて別々に描画しています。
サンプル3
入力
7 1 2 3 1 2 3 2 3 5 3 4 5 4 5 6 2 4 6 1 2 6
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。