308926: CF1599I. Desert
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Desert
题意翻译
### 题目描述 众所周知,一个无向图是仙人掌图当且仅当每条无向边至多属于一个环 。特别的,只有一个点的图也是仙人掌图 。 如果无向图的每一个连通块都是一个仙人掌图,那么我们称这个图是 “沙漠” 。( 类比树和森林之间的关系 ) 给定一个 $N$ 个点 $M$ 条边的无向图,边的编号分别为 $E_1,E_2…E_M$ 。 求数字对 $(L,R)$ 的个数 ,$(1\leq L\leq R\leq M)$,使得只由 $E_L,E_{L+1}…E_R$ 组成的无向图是 “沙漠” 。 ### 输入格式 第一行包含两个整数 $N$ 和 $M$ $(2\leq N\leq 2.5\times 10^5,1\leq M \leq 5\times 10^5)$ 。 接下来 $M$ 行,每行两个整数 $u_i,v_i$,表示一条边,其中 $E_i=(u_i,v_i)$,输入保证不存在自环 。 ### 输出格式 一行一个整数,表示问题的答案 。题目描述
You are given an undirected graph of $ N $ nodes and $ M $ edges, $ E_1, E_2, \dots E_M $ . A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus. Find the number of pairs $ (L, R) $ , ( $ 1 \leq L \leq R \leq M $ ) such that, if we delete all the edges except for $ E_L, E_{L+1}, \dots E_R $ , the graph is a desert.输入输出格式
输入格式
The first line contains two integers $ N $ and $ M $ ( $ 2 \leq N \leq 2.5 \times 10^5 $ , $ 1 \leq M \leq 5 \times 10^5 $ ). Each of the next $ M $ lines contains two integers. The $ i $ -th line describes the $ i $ -th edge. It contains integers $ U_i $ and $ V_i $ , the nodes connected by the $ i $ -th edge ( $ E_i=(U_i, V_i) $ ). It is guaranteed that $ 1 \leq U_i, V_i \leq N $ and $ U_i \neq V_i $ .
输出格式
The output contains one integer number – the answer.
输入输出样例
输入样例 #1
5 6
1 2
2 3
3 4
4 5
5 1
2 4
输出样例 #1
20
输入样例 #2
2 3
1 2
1 2
1 2
输出样例 #2
5