3715 . [模板題] Counting $C_4$'s

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

BaoCoder613

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

66.7% (8/12)

Tags

library-checker template

Description

You are given an undirected graph, consisting of $N$ vertices and $M$ edges. This graph may not be simple.
The $i$-th edge is $\lbrace u _ i, v _ i \rbrace$.

For each edge $i$, find $A _ i$ , as the number of unordered combinations of $3$ edges $x$ , $y$ , $z$
that those $4$ edges ( $i,x,y,z$ ) forms a subgraph isomorphic to $C _ 4$ ( A cycle with $4$ edges ).

Input Format

$N$ $M$
$u _ 0$ $v _ 0$
$u _ 1$ $v _ 1$
$\vdots$
$u _ {M-1}$ $v _ {M-1}$

Output Format

$A _ 0$ $A _ 1$ $\cdots$ $A _ {M-1}$

Sample Input 1

4 5
0 3
2 0
2 1
2 3
1 3

Sample Output 1

1 1 1 0 1

Sample Input 2

4 7
0 1
0 1
0 1
0 3
0 3
1 2
2 3

Sample Output 2

2 2 2 3 3 6 6

Hints

  • $2 \le N \le 3 \times 10^ 5$
  • $1 \le M \le 3 \times 10^ 5$
  • $0 \le u _ i \lt N$
  • $0 \le v _ i \lt N$
  • $u _ i \neq v _ i$

Problem Source

library checker: counting_c4

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 1048576 65536
1 5000 1048576 65536
2 5000 1048576 65536
3 5000 1048576 65536
4 5000 1048576 65536
5 5000 1048576 65536
6 5000 1048576 65536
7 5000 1048576 65536
8 5000 1048576 65536
9 5000 1048576 65536
10 5000 1048576 65536
11 5000 1048576 65536
12 5000 1048576 65536
13 5000 1048576 65536
14 5000 1048576 65536
15 5000 1048576 65536
16 5000 1048576 65536
17 5000 1048576 65536
18 5000 1048576 65536
19 5000 1048576 65536
20 5000 1048576 65536
21 5000 1048576 65536
22 5000 1048576 65536
23 5000 1048576 65536
24 5000 1048576 65536
25 5000 1048576 65536
26 5000 1048576 65536
27 5000 1048576 65536
28 5000 1048576 65536
Submit
Back to Top