HDU 3394 Railway(点双连通分量+桥)

HDU 3394 Railway(点双连通分量+桥)

http://acm.hdu.edu.cn/showproblem.php?pid=3394

题意:一个无向图(可能不连通)有n个点和m条边.现在要你找出冲突边和多余边的数目.其中冲突边是那些同时存在于多个环中的边,而多余边是不在任何一个环中的边.

分析:

首先我们可以知道多余边就是该无向图中的桥,桥必然不在任何环中.冲突边只能在点双连通分量中,而什么样的点双连通分量有冲突边呢?

对于有n个节点和n条边(或小于n条边,比如2点1边)的点双连通分量,这种分量只有一个大环,不存在其他任何环了,所以这种分量中的边都不是冲突边.

对于有n个节点和m条边(m>n)的点双连通分量来说,该分量内的所有边都是冲突边.因为边数>点数,所以该分量必有至少两个环,我们随便画个图就可知其中的任意边都至少在两个以上的环上.

综上所述,对于多余边,我们输出桥数.对于冲突边,我们输出边数>点数的点双连通分量的所有边数.

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=10000+10;
int n,m;
int ans1,ans2;//多余边,冲突边
vector<int> G[maxn];
int dfs_clock,bcc_cnt;
int pre[maxn],low[maxn],bcc[maxn],bccno[maxn];
struct Edge
{
    int u,v;
    Edge(int u,int v):u(u),v(v){}
};
stack<Edge> S;
void solve()
{
    bool vis[maxn];
    int sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=bcc[0];i++) vis[bcc[i]]=true;
    for(int i=1;i<=bcc[0];i++)
    {
        int u=bcc[i];
        for(int j=0;j<G[u].size();j++)
            if(vis[G[u][j]]) sum++;
    }
    sum /=2;
    if(sum>bcc[0]) ans2+= sum;
}
void tarjan(int u,int fa)
{
    low[u]=pre[u]=++dfs_clock;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) continue;
        Edge e=Edge(u,v);
        if(!pre[v])
        {
            S.push(e);
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=pre[u])//u是割点
            {
                if(low[v]>pre[u]) ans1++;
                bcc_cnt++;
                bcc[0]=0;
                while(true)
                {
                    Edge x=S.top(); S.pop();
                    if(bccno[x.u]!=bcc_cnt)
                    {
                        bcc[++bcc[0]]=x.u, bccno[x.u]=bcc_cnt;
                    }
                    if(bccno[x.v]!=bcc_cnt)
                    {
                        bcc[++bcc[0]]=x.v, bccno[x.v]=bcc_cnt;
                    }
                    if(x.u==u && x.v==v) break;
                }
                solve();
            }
        }
        else if(pre[v]< pre[u])
        {
            S.push(e);
            low[u]=min(pre[v],low[u]);
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        ans1=ans2=bcc_cnt=dfs_clock=0;
        memset(pre,0,sizeof(pre));
        memset(bccno,0,sizeof(bccno));
        for(int i=0;i<n;i++) G[i].clear();
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=0;i<n;i++)
            if(!pre[i]) tarjan(i,-1);
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}