美文网首页ACM - ICPC
Bridges Gym - 100712H (Tarjan缩点)

Bridges Gym - 100712H (Tarjan缩点)

作者: JesHrz | 来源:发表于2018-07-24 11:21 被阅读9次

题目来源: 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;
}

相关文章

  • Bridges Gym - 100712H (Tarjan缩点)

    题目来源: 2015 ACM Amman Collegiate Programming Contest State...

  • Gym - 100712H Bridges

    沉迷于连通分量了最后一道了 ,o((>ω< ))o不知道为什么乍看这道题感觉还挺简单,结果又是一个边连通分量+树的...

  • tarjan

    tarjan缩点的运用,寻找一个较小的点集使得从这些点出发能够到达任意不在点集中的点,若有多个点,输出这些集合升序...

  • 连通图

    Strongly Connected Componenet 割点(tarjan): 题目链接:Network(求割...

  • Golang桥接模式将多个chan桥接成一个chan

    bridges/bridges.go bridge_demo.go 程序输出如下,

  • Prettier

    Prettier There are bridges on the rivers, As ...

  • [Pink Floyd]Burning Bridges

    Pink Floyd《Burning Bridges》

  • Gym gym

    自从加入新的健身房之后,坚持一周三次上不同的力量训练和举铁高强度课,还尝试了拳击课和打击棍子的pound;四个星期...

  • tarjan

    tarjan:寻找出度为0的强连通分量,并求出该强连通分量中有多少个点。 sig表示的是强连通分量的个数其中col...

  • tarjan

    tarjan寻找出度为0的强连通分量,从小到大输出此强连通分量中的点 poj 2553 The Bottom of...

网友评论

    本文标题:Bridges Gym - 100712H (Tarjan缩点)

    本文链接:https://www.haomeiwen.com/subject/jisemftx.html