定义
若一个无向连通图不存在割边，则称它为“边双连通图”。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”
定理
一个图为边双连通图，当且仅当任意一条边都至少包含在一个简单环中。
求法
把图中所有桥删除，剩下的都是e-DCC。
具体方法：一般用Tarjan标记所有桥边，再用dfs求出各连通块个数（遍历时不走桥）。
常和缩点搭配：把e-DCC的编号当做节点，桥当做节点间的连边，则会形成一棵树或一座森林。
例题冗余路径
经典应用-构造边双连通分量：树的每一条边都是桥，但是给任意不同且不直接相连的两点加上一边后两点与其lca构成一个环，环上所有点为边强连通。由于题目要求连边最少，那么就使每次加的边让更多点边强连通。由上分析环的构造可知lca离两点越远对图上点贡献越多。那么每次将lca离两点最远的叶节点相连。本题不要求输出方案，所以因为每次都会
消掉两叶节点那么答案直接为（叶节点数 + 1）/2。（奇数剩余的一个点随便向其他点连边）。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
char c = getchar(),f = 1;x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') c = getchar(),f = -1;
for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
x *= f;
}
template<typename xxx> inline void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn = 200010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
struct edge{
int to,last,fg,from;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to) {
++tot;
e[tot].to = to;
e[tot].from = from;
e[tot].last = head[from];
head[from] = tot;
}
int n,m;
int dfn[maxn],low[maxn],cnt;
inline void tarjan(int x,int in_edge) {
dfn[x] = low[x] = ++cnt;
for(rint i = head[x];i; i = e[i].last) {
if(!dfn[e[i].to]) {
tarjan(e[i].to,i);
if(low[e[i].to] < low[x]) low[x] = low[e[i].to];
if(low[e[i].to] > dfn[x]) {
e[i].fg = e[i^1].fg = 1;
}
}
else if(i ^ (in_edge ^ 1) && dfn[e[i].to] < low[x]) low[x] = dfn[e[i].to];
}
}
int col[maxn],num,in[maxn];
inline void ddfs(int x) {
col[x] = num;
for(rint i = head[x];i;i = e[i].last) {
if(col[e[i].to] || e[i].fg) continue;
ddfs(e[i].to);
}
}
int main()
{
read(n);read(m);tot = 1;
for(rint i = 1;i <= m; ++i) {
int x,y;
read(x);read(y);
add(x,y);add(y,x);
}
for(rint i = 1;i <= n; ++i) {
if(!dfn[i]) {
tarjan(i,0);
}
}
for(rint i = 1;i <= n; ++i) {
if(!col[i]) {
++num;
ddfs(i);
}
}
for(rint i = 2;i <= tot; ++i) {
if(col[e[i].from] == col[e[i].to]) continue;
++in[col[e[i].from]];
++in[col[e[i].to]];
}
int ans = 0;
for(rint i = 1;i <= num; ++i)
if(in[i] == 2) ++ans;
print((ans + 1) / 2);
return 0;
}
/*
*/