沉迷于連通分量了
最后一道了 ，o((>ω< ))o
不知道為什么乍看這道題感覺還挺簡(jiǎn)單，結(jié)果又是一個(gè)邊連通分量+樹的直徑問題
樹的直徑已經(jīng)被虐過一道了，真的難受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

這個(gè)題其實(shí)比上一道還要簡(jiǎn)單一點(diǎn)
只需要求出縮點(diǎn)后點(diǎn)的數(shù)量 - 樹的直徑的長(zhǎng)度

#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);
    }
}