题目#
F (1≤F≤5000) 个草场の間を移動するために、ベッキーと彼女の仲間たちは時々彼女たちが嫌いな恐ろしい木を通らなければならないことがあります。牛たちは特定の道を強制的に歩かされることに飽きてしまったので、彼女たちは草場のペア間に少なくとも 2 つの相互に分離された道があるように新しい道を建設したいと考えています。そうすれば、彼女たちは選択肢が増えます。
草場のペア間にはすでに少なくとも 1 つの道があります。すべての R (F-1≤R≤10000) 条の双方向の道の説明が与えられ、各道は 2 つの異なる草場を接続しています。新たに建設する必要がある道の最小数を計算してください。道は複数の道が首尾よく接続されて形成されます。2 つの道が相互に分離されているとは、2 つの道が重複する道を持たないことを意味します。ただし、2 つの分離された道にはいくつかの同じ草場が含まれていても構いません。同じ草場のペア間には、すでに 2 つの異なる道がある場合もあり、それらの間にさらに 1 つの道を建設して別の異なる道とすることもできます。
入力フォーマット：
行 1：スペースで区切られた 2 つの整数：F と R
行 2..R+1：各行には、ある道の端点にある草場の 2 つのスペースで区切られた整数が含まれています。
出力フォーマット：
行 1：新たに建設する必要がある道の数を示す単一の整数。
入力出力サンプル
入力サンプル #1：
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
出力サンプル #1：
2
思路#
これは一本通のテンプレート問題です。橋を持つ連結グラフが辺を追加して辺双連結グラフに変わるために必要な辺の数を求めます。まず、すべての橋を削除し、残ったのは辺双連結成分です。各辺双連結成分を 1 つの頂点に縮小し、橋を戻すと、最後に残るのは木になります。
この木の葉ノードの数を leaf とすると、必要な辺の数はleaf == 1 ? 0 : (leaf + 1) / 2です。ここでの除算は整数除算です。
これはテスト済みです！！
コード#
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
using std::stack;
using std::min;
const int MAXN = 40000 + 5;
namespace m1 {
struct ed {
int to, nex, frm;
} e[MAXN];
int head[MAXN];
int newp = 1;
int low[MAXN], dfn[MAXN], out[MAXN];
int tim;
int dcnt;//双連結成分番号
int dcolor[MAXN];//双連結成分の色付け
bool bridge[MAXN];
void insert (int p1, int p2);
void tarjan (int p, int ed);
void dfs (int p);
}
int n, m;
int main (void) {
{
using namespace m1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
insert(x, y);
insert(y, x);
}
tarjan(1, 0);
for (int i = 1; i <= n; ++i) {
if (!dcolor[i]) {
++dcnt;
dfs(i);
}
}
for (int i = 1; i <= m; ++i) {
if (dcolor[e[i * 2].frm] != dcolor[e[i * 2].to]) {
++out[dcolor[e[i * 2].frm]];
++out[dcolor[e[i * 2].to]];
}
}
int leaf = 0;
for (int i = 1; i <= dcnt; ++i) {
if (out[i] == 1) {
++leaf;
}
}
printf("%d\n", leaf == 1 ? 0 : (leaf + 1) / 2);
}
return 0;
}
void m1::insert (int p1, int p2) {
++newp;
e[newp].frm = p1;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
void m1::tarjan (int p, int ed) {
dfn[p] = low[p] = ++tim;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (!dfn[y]) {
tarjan(y, i);
low[p] = min(low[p], low[y]);
if (dfn[p] < low[y]) {
bridge[i] = bridge[i ^ 1] = 1;
}
}
else if (i != (ed ^ 1)) {
low[p] = min(low[p], dfn[y]);
}
}
}
void m1::dfs (int p) {
using namespace m1;
dcolor[p] = dcnt;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (dcolor[y] != 0 || bridge[i] == 1) {
continue;
}
dfs(y);
}
}