题目大意
给你一个有重边的无向图图，问你最少连接多少条边可以使得整个图双联通
思路
就是个边双的模板
注意判重边的时候只对父亲节点需要考虑
你就dfs的时候记录一下出现了多少条连向父亲的边就可以了
然后和有向图不一样的是，在这里非树边的更新不用判断点是不是在栈内，因为无向图中没有u可以到达v但是v不能到达u的情况
//Author: dream_maker
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = 1;x = 0;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = 0, c = getchar();
while (isdigit(c)) {
x = (x<<1) + (x<<3) + c -'0';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) Write(x / 10);
putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 5e3 + 10;
const int M = 1e4 + 10;
struct Edge {
int u, v, nxt;
} E[M << 1];
int head[N], tot = 0;
int n, m, du[N];
void add(int u, int v) {
++tot;
E[tot].u = u;
E[tot].v = v;
E[tot].nxt = head[u];
head[u] = tot;
}
int dfn[N], low[N], bel[N], ind = 0, cnt_bcc = 0;
stack<int> st;
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ind;
st.push(u);
bool k = 0;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (fa == v && !k) {
k = 1;
continue;
}
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
int now;
++cnt_bcc;
do {
now = st.top(); st.pop();
bel[now] = cnt_bcc;
} while (now != u);
}
}
int main() {
Read(n), Read(m);
fu(i, 1, m) {
int u, v;
Read(u), Read(v);
add(u, v);
add(v, u);
}
fu(i, 1, n) if (!dfn[i]) tarjan(i, 0);
for (int i = 1; i <= tot; i += 2) {
int u = E[i].u, v = E[i].v;
if (bel[u] != bel[v]) {
du[bel[u]]++;
du[bel[v]]++;
}
}
int ans = 0;
fu(i, 1, cnt_bcc)
if (du[i] == 1) ans++;
ans = (ans + 1) >> 1;
Write(ans);
return 0;
}