Count Simple Paths

题目描述

你被给定了一个简单无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。每个顶点的度数最多为 $10$。
令 $K$ 为从顶点 $1$ 出发的简单路径（不重复顶点的路径）的数量。输出 $\min(K, 10^6)$。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

输出答案。

4 2
1 2
2 3

3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

16

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

2023

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)$ $1 \leq u_i, v_i \leq N$ 给定的图是简单图。 给定图中每个顶点的度数最多为 $10$。
输入中的所有数值都是整数。我们有以下三条计数的路径。（注意长度为 $0$ 的路径也计数。）

顶点 $1$； 顶点 $1$、顶点 $2$； 顶点 $1$、顶点 $2$、顶点 $3$。

标签: AtCoder|abc284E

来源

AtCoder|abc284E