Bridges Gym - 100712H (Tarjan缩点)

题目来源： 2015 ACM Amman Collegiate Programming Contest

Statement

An edge in an undirected graph is a bridge​if 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 N​is the number of nodes, and M​is the number of edges.

Each of the following M​lines contains two space-separated integers: X Y (1 ≤ X, Y ≤ N)(X ≠ Y)​, which means that there is an edge between node X​and 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;
}