题目大意：给出一张无向图，如果要让每两点之间都有两条不同的路径可以相互到达，，问至少还要添加几条边
解题思路：添加的边的数量就是(入度为1的点 ＋ 1) ／2,也就是所有连通分量缩图后，形成的树的(叶子结点＋1) ／ 2 这题和前面做过的类似，这里只是搬运了一下别人的另一种写法 如果属于同一个连通分量的话，那么他们的lowlink是一样的，所以可以用来直接判断，而不需要再dfs的时候再把每个点归属到所属的连通分量内
N 5010Edge{int from, to, next;}E[M];bool repeat[N][N], vis[M];int pre[N], lowlink[N], head[N], in[N];int n, m, tot, dfs_clock;void AddEdge(int u, int v) {E[tot].from = u;E[tot].to = v;E[tot].next = head[u];head[u] = tot++;}void init() {scanf(“%d%d”, &n, &m);memset(head, -1, sizeof(head));tot = 0;int u, v;for (int i = 0; i < m; i++) {scanf(“%d%d”, &u, &v);if (repeat[u][v] || repeat[v][u])continue;repeat[u][v] = repeat[v][u] = true;AddEdge(u, v);AddEdge(v, u);}}void dfs(int u, int fa) {lowlink[u] = pre[u] = ++dfs_clock;for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (vis[i]) continue;vis[i] = vis[i ^ 1] = true;if (!pre[v]) {dfs(v, u);lowlink[u] = min(lowlink[u], lowlink[v]);}else if (v != fa) {lowlink[u] = min(lowlink[u], pre[v]);}}}void solve() {dfs_clock = 0;dfs(1,0);int u, v;for (int i = 0; i < tot; i++) {u = lowlink[E[i].from];v = lowlink[E[i].to];if (u != v)in[v]++;}int ans = 0;for (int i = 1; i <= n; i++)if (in[i] == 1)ans++;printf(“%d\n”, (ans + 1) / 2);}int main() {init();solve();return 0;}
收敛自己的脾气，偶尔要刻意沉默，
