No.488 四角関係
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 235
作問者 : 小指が強い人 / テスター : tatuyan_edson
タグ : / 解いたユーザー数 235
作問者 : 小指が強い人 / テスター : tatuyan_edson
問題文最終更新日: 2017-02-26 00:27:36
問題文
$N$個のノードが$0$番から$N-1$番まで番号が割り当てられています。
そして、ノードは互いに関係を持っているノードもあれば持っていないノードもあります。
そのノードの集合の中で四角の関係を持つものの数を出力してください。
ここで言う四角の関係とは、4つのノードだけで考えた時、それが$4$点の閉路グラフであることを言います。
(その4点中の3点では閉路を作れないということである。)
入力
$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $⋮$ $⋮$ $a_{M-1}$ $b_{M-1}$ $a_M$ $b_M$
$N$はノードの個数です。
$M$は関係を持つノードの組の個数を表します。
$a_i$と$b_i$は、ノードの番号を表し、$a_i$と$b_i$に関係を持っていることを表します。
$2 \le N \le 50$ (整数)
$1 \le M \le \frac{N \times (N - 1)}{2}$ (整数)
$0 \le a_i < b_i < N$ (整数)
$(a_i,b_i) \ne (a_j,b_j)$
$i=1...M$
出力
$X$
問題文の答えを一つ出力してください。
サンプル
サンプル1
入力
6 8 0 1 1 2 2 3 0 2 0 3 3 4 4 5 0 5
出力
1
上の図は、サンプル1のノードの関係の図です。
{0,1,2,3}と{0,3,4,5}の2つですが、{0,1,2,3}は0と2に関係を持っているので除きます。
したがって、答えは1です。
サンプル2
入力
3 3 0 1 1 2 0 2
出力
0
3つのノードで四角の関係を持つことはありません。
サンプル3
入力
8 17 0 3 0 4 0 6 1 2 1 6 2 4 2 5 2 7 3 4 3 5 3 6 4 5 4 6 4 7 5 6 5 7 6 7
出力
3
{1,2,5,6},{1,2,7,6},{1,2,4,6}の3つが条件を満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。