P5272: 简单路径

---

【题目描述】

题目描述
给定一个由 n 个点、n 条边组成的无向连通图，这张图不存在重边，也不存在自环。请问在这张图上，存在多少条简单路径？
所谓简单，是指路径的起点与终点不相同，且路径上的任何点、任何边都不会在路径上重复出现。所谓重边，是指两条不同的边，连接了同一对点。所谓自环，是指一条边，连接了同一个点。
输入格式
第一行：单个正整数表示 n；
第二行到第 n+1行：每行两个点 u和 v，表示一条边连接了编号为 u 与 v 的点。图的结点编号为 1 到 n之间的整数。
输出格式
单个整数：表示简单路径的条数，由于数字可能很大，输出答案模 10⁹+7的余数。
数据范围
对于 30% 的数据，n≤200；
对于 50% 的数据，n≤2000；
对于 70% 的数据，n≤20000；
对于 100% 的数据，3≤n≤200000。
样例数据
输入:
3
1 2
2 3
3 1
输出:
12
说明:
1->2
2->1
1->3
3->1
2->3
3->2
1->2->3
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1
输入:
6
1 2
2 3
3 1
1 4
1 5
2 6
输出:
52
 

题目类型~

第二届青少年算法竞赛(中学组) 

咻咻~

提交答案 状态 返回