Gym - 100712H Bridges

沉迷于连通分量了
最后一道了 ，o((>ω< ))o
不知道为什么乍看这道题感觉还挺简单，结果又是一个边连通分量+树的直径问题
树的直径已经被虐过一道了，真的难受T.T~

H. Bridges
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

这个题其实比上一道还要简单一点
只需要求出缩点后点的数量 - 树的直径的长度

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#define LL long long
using namespace std;
const int maxn = 100010;
const LL inf = 0xffffffffff;
int n,m;
int dfn[maxn],low[maxn],belong[maxn];
int cnt,index;
struct node
{
    int u,v,w;
}s[maxn];
vector<int >G[maxn];
vector<node> g[maxn];
stack<int >S;
void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    for(int i=0;i<=n;i++)
    {
        G[i].clear();g[i].clear();
    }
    cnt = index = 0;
}
void Tarjan(int u,int pre)
{
    dfn[u] = low[u] = ++index;
    S.push(u);
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(v == pre)  continue;
        if(!dfn[v])
        {
            Tarjan(v,u);
            low[u] = min(low[u],low[v]);
        }
        else low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        int gg;
        ++cnt;
        while(1)
        {
            gg = S.top();
            S.pop();
            belong[gg] = cnt;
            if(gg==u)  break;
        }
    }
}



int max_len,st;

void TreeDia(int u,int pre,int len)
{
    if(len > max_len) st = u,max_len = len;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i].v;
        if(v==pre)  continue;
        TreeDia(v,u,len+g[u][i].w);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i = 0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            s[i].u = a,s[i].v = b,s[i].w = 1;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        Tarjan(1,-1);

        for(int i=0;i<m;i++)
        {

                int u = belong[s[i].u];
                int v = belong[s[i].v];
                int w = s[i].w;
                if(u!=v)
                {
                    //printf("u = %d,v = %d\n",u,v);
                    g[u].push_back((node){0,v,w});
                    g[v].push_back((node){0,u,w});
                }

        }
        max_len = -1;
        TreeDia(1,-1,0);
        TreeDia(st,-1,0);
        //printf("cnt = %d , max_len = %d\n",cnt,max_len);
        printf("%d\n",cnt-max_len-1);
    }
}