P1889 - 奶牛联盟 - New Online Judge

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

Bessie 和她来自附近农场的牛伙伴们最终决定，他们将开始通过小径将他们的农场连接在一起，以努力形成一个反对农民的联盟。
N个农场中每个农场的奶牛最初都被指示建造一条通往另一个农场的路径，总共有 N 条路径。
然而，在项目实施几个月后，实际上只建成了 M 条路径。

Bessie 希望计算出目前存在的 M 条路径有多少种方案可以建造。
例如，如果有一条路径连接农场 3 和 4，那么一种可能性是农场 3 建造了这条路径，另一种可能性是农场 4 建造了这条路径。
帮助 Bessie 计算为建造它们的农场分配的不同路径的数量，以 1,000,000,007 为模。
如果在两个方案中至少有一条由不同农场建造的路径，则认为两个方案不同。

输入第一行为正整数 N 和 M，1 <= N <= 100,000， 1 <= M < N。
接下来 M 行，每行两个正整数 ui，vi，表示存在一条连接农场 ui 和农场 vi 的路径。
1 <= ui, vi <= N, ui != vi。

总共有6个可能的方案。 {a，b，c，d}表示农场a构建路径1，农场b建造路径2，农场c构建路径3，农场d建造路径4。

{2, 3, 4, 5} 
{2, 3, 5, 4} 
{1, 3, 4, 5} 
{1, 3, 5, 4} 
{1, 2, 4, 5} 
{1, 2, 5, 4}

来源：USACO 2012.1

进阶题连通性 USACO

1889: 奶牛联盟

题目描述

输入格式

输入样例复制

输出样例复制

数据范围与提示

分类标签