AT_abc284_e [ABC284E] Count Simple Paths

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。此外，每个顶点的度数都不超过 $10$。

请计算以顶点 $1$ 为起点的所有简单路径（即不经过同一顶点多次的路径）的数量，记为 $K$。请输出 $\min(K,\ 10^6)$。

输入格式

输入以以下格式从标准输入给出。

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 2
1 2
2 3

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

16

输入输出样例 #3

输入 #3

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

输出 #3

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$
• 输入的所有值均为整数

样例解释 1

满足条件的路径有以下 $3$ 个（注意长度为 $0$ 的路径也要计数）：

• 顶点 $1$
• 顶点 $1$，顶点 $2$
• 顶点 $1$，顶点 $2$，顶点 $3$

由 ChatGPT 4.1 翻译