No.488 Square Relationship
タグ : / 解いたユーザー数 244
作問者 :
小指が強い人
/ テスター :
tatuyan_edson
Problem Statement
$N$ nodes are numbered from $0$ to $N-1$.
Some nodes have relationships with each other, and some do not.
Output the number of square relationships in this set of nodes.
Here, a square relationship means that, when considering only those 4 nodes, they form a cycle graph on $4$ vertices.
(That is, no cycle can be formed by 3 of those 4 points.)
Input
$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$⋮$ $⋮$
$a_{M-1}$ $b_{M-1}$
$a_M$ $b_M$
$N$ is the number of nodes.
$M$ is the number of pairs of nodes that have a relationship.
$a_i$ and $b_i$ are node numbers, indicating that $a_i$ and $b_i$ have a relationship.
$2 \le N \le 50$ (integer)
$1 \le M \le \frac{N \times (N - 1)}{2}$ (integer)
$0 \le a_i < b_i < N$ (integer)
$(a_i,b_i) \ne (a_j,b_j)$
$i=1...M$
Output
$X$
Output one value, the answer to the problem.
Sample
Sample 1
Input
6 8 0 1 1 2 2 3 0 2 0 3 3 4 4 5 0 5
Output
1
The figure above shows the node relationships in Sample 1.
There are two candidates, {0,1,2,3} and {0,3,4,5}, but {0,1,2,3} is excluded because 0 and 2 have a relationship.
Therefore, the answer is 1.
Sample 2
Input
3 3 0 1 1 2 0 2
Output
0
With 3 nodes, there can be no square relationship.
Sample 3
Input
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
Output
3
The 3 sets {1,2,5,6}, {1,2,7,6}, and {1,2,4,6} satisfy the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。