[蓝桥杯 2013 国 AC] 网络寻路

Luogu
IDLGP8605
Time1000ms
Memory64MB
DifficultyP2
图论2013蓝桥杯国赛
$X$ 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。 源地址和目标地址可以相同,但中间节点必须不同。 如图 $1$ 所示的网络: ![](https://cdn.luogu.com.cn/upload/image_hosting/asqw8dfi.png) $1 \to 2 \to 3 \to 1$ 是允许的。 $1 \to 2 \to 1 \to 2$ 或者 $1 \to 2 \to 3 \to 2$ 都是非法的。 ## Input 输入数据的第一行为两个整数 $N,M$,分别表示节点个数和连接线路的条数 $(1 \le N \le 10000,0 \le M \le 100000)$。 接下去有 $M$ 行,每行为两个整数 $u$ 和 $v$,表示节点 $u$ 和 $v$ 联通 $(1 \le u,v \le N,u \neq v)$。 输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环。 ## Output 输出一个整数,表示满足要求的路径条数。 [samples] ## Note 时限 1 秒,空间限制 64M。蓝桥杯 2013 年第四届国赛 ------------ 2024/1/28 添加一组 hack 数据
Samples
Input #1
3 3
1 2
2 3
1 3
Output #1
6
Input #2
4 4
1 2
2 3
3 1
1 4
Output #2
10
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2013 国 AC] 网络寻路",
    "description": {
      "content": "$X$ 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。 源地址和目标地址可以相同,但中间节点必须不同。 如图 $1$ 所示的网络: ![](https://cdn.luogu.com.cn/upload/image_hosting/asqw8",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8605"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$X$ 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。\n\n源地址和目标地址可以相同,但中间节点必须不同。\n\n如图 $1$ 所示的网络:\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/asqw8...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments