zoj4097

题意：
模版题，给你一幅图，问你最少加几条边，使得图变成一个双联通分量。

模版

// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>

using namespace std;

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],d[maxn],cnt;
    void ini(int n){
        for(int i=0;i<=n;i++) head[i]=-1;
        for(int i=0;i<=n;i++) d[i]=0;
        cnt=-1;
    }
    void add_edge(int u,int v){
        edge[++cnt]=star{v,head[u]};
        head[u]=cnt;
        edge[++cnt]=star{u,head[v]};
        head[v]=cnt;
        d[u]++;
        d[v]++;
    }
}tree;

struct Tarjan:Graph{//双联通分量, 割边, 桥, 边双联通缩点
    struct Bridge{int u,v;}bridge[maxn];
    int dfn[maxn],low[maxn],belong[maxn],vis[maxn],sta[maxn],sta_,nums,bridge_;
    void ini(int n){
        for(int i=0;i<=n;i++) vis[i]=0;
        bridge_=0;
        nums=0;
        Graph::ini(n);
    }
    void tarjan(int u,int father,int&step){
        low[u]=dfn[u]=++step;
        sta[++sta_]=u;
        vis[u]=1;
        bool firsttimes=true;//用于判重边
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&firsttimes) {
                firsttimes=false;
                continue;
            }//父边
            if(vis[v]==1) low[u]=min(low[u],dfn[v]);//回边,终点在栈中
            else {//树边
                tarjan(v,u,step);
                low[u]=min(low[u],low[v]);
                if(low[v]>dfn[u]) bridge[++bridge_]=Bridge{u,v};
            }
        }
        if(low[u]==dfn[u]){
            while(sta[sta_]!=u) belong[sta[sta_--]]=nums+1;
            belong[sta[sta_--]]=++nums;
        }
    }
}graph;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
    int n=read(),m=read();
    graph.ini(n);
    for(int i=0;i<m;i++) graph.add_edge(read(),read());
    int step=0;
    graph.tarjan(1,0,step);

    tree.ini(graph.nums);
    for(int i=1;i<=graph.bridge_;i++){
        int u=graph.bridge[i].u,v=graph.bridge[i].v;
        tree.add_edge(graph.belong[u],graph.belong[v]);
    }
    int ans=0;
    for(int i=1;i<=graph.nums;i++){
        if(tree.d[i]==1) {
            ans++;
        }
    }
    cout<<(ans+1)/2<<endl;
}