沉迷于連通分量了
最后一道了 ，o((>ω< ))o
不知道為什么乍看這道題感覺還挺簡單扳躬，結(jié)果又是一個邊連通分量+樹的直徑問題
樹的直徑已經(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

這個題其實比上一道還要簡單一點
只需要求出縮點后點的數(shù)量 - 樹的直徑的長度

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