构造双连通（tarjan）

题目：

给定一个N个顶点，M条边的无向连通图，顶点从1到N编号。

问至少要添加几条边，才能使其变为双连通图。

输入

第一行包含两个整数N, M (3 le N, M le 1000)N,M(3≤N,M≤1000)。

接下来M行，每行两个整数u, v(1 le u, v le N)u,v(1≤u,v≤N)，表示u, vu,v之间一条无向边相连。

输入保证是一个连通图。

输出

输出最少添加几条边使得其变成双连通图。

样例

输入

复制

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

输出

2

输入

3 3
1 2
2 3
1 3

输出

0

/*************************************************************************
  > Author: Henry Chen
  > Mail: 390989083@qq.com 
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;

int head[maxn],nxt[maxn*2],tot;
int n,m;
int flag[maxn];
int low[maxn],dfn[maxn];
int st[maxn],inst[maxn];
int tp;
int tt,cnt;
int f[maxn];

struct edge
{
    int v;
    bool ck;
}e[maxn*2];

void add_edge(int u,int v)
{
    e[tot].v = v;
    e[tot].ck = false;
    nxt[tot] = head[u];
    head[u] = tot;
    tot++;
}

void tarjan(int u,int fa)
{
    //cout << u << endl;
    dfn[u] = low[u] = ++tt;
    st[tp++] = u;
    inst[u] = 1;
    for(int i = head[u];i != -1;i = nxt[i])
    {
        int v = e[i].v;
        //printf("%d %d
",v,dfn[v]);
        if(v == fa) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            if(low[u] > low[v])
            {
                low[u] = low[v];
            }
            if(dfn[u] < low[v])
            {
                e[i].ck = true;
                e[i^1].ck = true;
            }
        }
        else if(inst[v] && low[u] > dfn[v])
        {
            low[u] = dfn[v];
        }
    }
    if(low[u] == dfn[u])
    {
        int v;
        cnt++;
        v = st[--tp];
        inst[v] = 0;
        f[v] = cnt;
        while(u != v)
        {
            v = st[--tp];
            inst[v] = 0;
            f[v] = cnt;
        }
    }
}


int main()
{
    cin >> n >> m;
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(inst,0,sizeof(inst));
    memset(flag,0,sizeof(flag));
    tot = 0;
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    tp = 0;
    tt = 0;
    cnt = 0;
    tarjan(1,1);
    for(int u = 1;u <= n;u++)
    {
        for(int i = head[u];i != -1;i = nxt[i])
        {
            //printf("%d %d
",i,e[i].ck);
            if(e[i].ck)
            {
                flag[f[u]]++;
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= cnt;i++)
    {
        if(flag[i] == 1)
        {
            ans++;
        }
    }
    printf("%d
",(ans+1)/2);
    return 0;
}