UVA-10972 RevolC FaeLoN （边双连通+缩点）

题目大意：将n个点，m条边的无向图变成强连通图，最少需要加几条有向边。

题目分析：所谓强连通，就是无向图中任意两点可互达。找出所有的边连通分量，每一个边连通分量都是强连通的，那么缩点得到bcc图，只需考虑在bcc图上加有向边。如果，bcc图是由v个孤立的点，0条边构成的，则最少需要添加v条（将v个点首尾顺次连起来构成一条圈）有向边。如果由v个点，k条边构成，则对于每一个顶点，如果度数大于2，就不用给它加任何边，因为它一定能会在圈中；如果度数为1，则为这个点添只加一条边即可；如果度数为0，也就是孤立点，要想连在圈中，必须添加两条边。最后，考虑到重复，把累加和除以2后向上取整便是答案。

找边双连通分量套模板。。。标记每一个桥，再深搜一次，过程中不经过桥。

代码如下：

# include<iostream>

# include<cstdio>

# include<vector>

# include<stack>

# include<cstring>

# include<algorithm>

using namespace std;

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

struct Edge

{

    int to,flag;

    Edge(int v,int f):to(v),flag(f){}

};

const int N=1005;

int n,m,bcc_cnt,dfs_clock,low[N],pre[N],bccno[N],du[N];

vector<int>G[N];

vector<Edge>e;

void dfs(int u,int fa)

{

    low[u]=pre[u]=++dfs_clock;

    REP(i,0,G[u].size()){

        int v=e[G[u][i]].to;

        if(!pre[v]){

            dfs(v,u);

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

            if(low[v]>low[u])

                e[G[u][i]].flag=e[G[u][i]^1].flag=1;

        }else if(pre[v]<pre[u]&&v!=fa)

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

    }

}

void dfs1(int u)

{

    bccno[u]=bcc_cnt;

    REP(i,0,G[u].size()){

        int v=e[G[u][i]].to;

        if(!bccno[v]&&!e[G[u][i]].flag) dfs1(v);

    }

}

void findBcc()

{

    CL(bccno,0);

    CL(pre,0);

    dfs_clock=bcc_cnt=0;

    REP(i,0,n) if(!pre[i]) dfs(i,-1);

    REP(i,0,n) if(!bccno[i]){

        ++bcc_cnt;

        dfs1(i);

    }

}

int main()

{

    int a,b;

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

    {

        e.clear();

        REP(i,0,n) G[i].clear();

        while(m--)

        {

            scanf("%d%d",&a,&b);

            --a,--b;

            e.push_back(Edge(b,0));

            e.push_back(Edge(a,0));

            G[a].push_back(e.size()-2);

            G[b].push_back(e.size()-1);

        }

        findBcc();

        if(bcc_cnt==1){

            printf("0\n");

            continue;

        }

        CL(du,0);

        REP(u,0,n){

            REP(i,0,G[u].size()){

                int v=e[G[u][i]].to;

                if(bccno[u]!=bccno[v])  ++du[bccno[v]];

            }

        }

        int ans=0;

        REP(i,1,bcc_cnt+1){

            if(du[i]==1) ++ans;

            if(du[i]==0) ans+=2;

        }

        printf("%d\n",(ans+1)/2);

    }

    return 0;

}

巴特西

UVA-10972 RevolC FaeLoN （边双连通+缩点）

最新文章

热门文章