题目来源: 2015 ACM Amman Collegiate Programming Contest
Statement
An edge in an undirected graph is a bridgeif after removing it the graph will be disconnected.
Given an undirected connected graph, you are allowed to add one edge between any pair of nodes so that the total number of bridges in the graph is minimized.
Input
The first line of input contains T (1 ≤ T ≤ 64)that represents the number of test cases.
The first line of each test case contains two integers: N (3 ≤ N ≤ 100,000) and M (N-1 ≤ M ≤ 100,000), where Nis the number of nodes, and Mis the number of edges.
Each of the following Mlines contains two space-separated integers: X Y (1 ≤ X, Y ≤ N)(X ≠ Y), which means that there is an edge between node Xand node Y.
It is guaranteed that each pair of nodes is connected by at most one edge.
Test cases are separated by a blank line.
Output
For each test case, print a single line with the minimum possible number of bridges after adding one edge.
Sample Input
2
7 7
1 2
2 3
3 1
3 4
4 5
4 6
6 7
3 3
1 2
2 3
3 1
Sample Output
1
0
题意
给你一个连通的无向图,问你在这个图中如果任意添加一条边后,图中的割边最少有几条
思路
tarjan求原图的割边数tot,并且将连通分量缩点构成一个新图,新图是一棵树,tot减去树深为答案
#include <bits/stdc++.h>
using namespace std;
vector<int>g[100005];
struct edge
{
int v, w;
edge(int _v, int _w) :v(_v), w(_w) {}
};
vector<edge>e[100005];
bool vis[100005];
int n, m;
int f[100005], dfn[100005], low[100005];
int dep[100005];
int index, tot, ans;
void Tarjan(int u, int fa)
{
f[u] = fa;
dfn[u] = low[u] = ++index;
int len = g[u].size();
for (int i = 0; i < len; ++i)
{
int v = g[u][i];
if (!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if (v != fa)
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
if (fa)
{
tot++;
e[fa].push_back(edge(u, 1));
e[u].push_back(edge(fa, 1));
}
}
else
{
if (fa)
{
e[fa].push_back(edge(u, 0));
e[u].push_back(edge(fa, 0));
}
}
}
void dfs(int u)
{
vis[u] = true;
int len = e[u].size();
for (int i = 0; i < len; ++i)
{
edge cur = e[u][i];
if (!vis[cur.v])
{
dep[cur.v] = dep[u] + cur.w;
dfs(cur.v);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
memset(f, 0, sizeof(f));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(dep, 0, sizeof(dep));
memset(vis, false, sizeof(vis));
index = tot = ans = 0;
for (int i = 1; i <= n; ++i)
g[i].clear(), e[i].clear();
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
Tarjan(1, 0);
dfs(1);
int pos = 0;
for (int i = 1; i <= n; ++i)
{
if (dep[i] > ans)
{
ans = dep[i];
pos = i;
}
}
if (pos == 0)
ans = 0;
else
{
memset(vis, false, sizeof(vis));
memset(dep, 0, sizeof(dep));
dfs(pos);
for (int i = 1; i <= n; ++i)
ans = max(dep[i], ans);
}
cout << tot - ans << endl;
}
return 0;
}
网友评论