poj 3352 : Road Construction 【ebcc】

题目链接

题意：给出一个连通图，求最少加入多少条边可使图变成一个 边-双连通分量

模板题，熟悉一下边连通分量的定义。最后ans=(leaf+1)/2。leaf为原图中size为1的边-双连通分量

#include<cstdio>

#include<vector>

#include<algorithm>

#include<stack>

#include<cstring>

using namespace std;

const int maxn=;

int n,m;

vector<int> adj[maxn];

int dfn[maxn],low[maxn];

int time_tag;

int ebccno[maxn],ebcc_cnt;

int size[maxn];    //size[i]用来记录编号为i的ebcc的size

stack<int> st;

void init()

{

    memset(dfn,,sizeof(dfn));

    memset(size,,sizeof(size));

    memset(ebccno,,sizeof(ebccno));

    time_tag=ebcc_cnt=;

    for(int i=;i<=n;i++)

        adj[i].clear();

}

void dfs(int u,int pre)

{

    dfn[u]=low[u]=++time_tag;

    st.push(u);

//    for(int v:adj[u])

    for(int i=;i<adj[u].size();i++)

    {

        int v=adj[u][i];

        if(v==pre) continue;

        if(!dfn[v])

        {

            dfs(v,u);

            low[u]=min(low[u],low[v]);

        }

        else

            low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u])

    {

        ++ebcc_cnt;

        while()

        {

            int x=st.top();st.pop();

            ebccno[x]=ebcc_cnt;

            if(x==u) break;

        }

    }

}

void find_ebcc()

{

    for(int i=;i<=n;i++)

        if(!dfn[i]) dfs(i,-);

}

int solve()

{

    int ret=;

    for(int u=;u<=n;u++)

//        for(int v:adj[u])

        for(int i=;i<adj[u].size();i++)

        {

            int v=adj[u][i];

            if(ebccno[u]!=ebccno[v])    //边(u,v)为bridge

                size[ebccno[u]]++,size[ebccno[v]]++;

        }

    for(int i=;i<=ebcc_cnt;i++)

        if(size[i]==) ret++;

    return ret;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

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

        {

            int u,v;

            scanf("%d%d",&u,&v);

            adj[u].push_back(v);

            adj[v].push_back(u);

        }

        find_ebcc();

        int leaf=solve();

        printf("%d\n",(leaf+)/);

    }

}