您当前位置：首页 > php开源 > php教程 > HDU3394.Railway――点双连通分量

HDU3394.Railway――点双连通分量

来源：程序员人生发布时间：2015-05-07 09:06:48 阅读次数：3469次

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

题目描写：
有1个公园有n个景点，公园的管理员准备修建m条道路，并且安排1些构成回路的参观线路。如果1条道路被多条道路公用，那末这条路是冲突的；如果1条道路没在任何1个回路内，那末这条路是不冲突的

问分别有多少条有冲突的路和没有冲突的路

分析：
刚学点双和边双，看见题目分不清哪一个是哪一个~

这个题目是求点双的。某条边有冲突，说明该点双连通份量中存在两个以上的环，没有冲突说明这条边是桥

怎样判断1个双连通份量中环的个数呢？根据点数跟边数的关系
1.当点数=边数，构成1个环
2.当点数>边数（1条线段，说明这条边是桥）
3.当点数<边数，那末就含1个以上的环了

//296MS 3624K   2190 B
#include<cstring>
#include<cstdio>
#include<iostream>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,a,b) for(int i=(a);i<(b);++i)
#define max(a,b) (a<b?b:a)
const int MAXN=10010;
const int MAXM=100010;
using namespace std;
int low[MAXN],dfn[MAXN],Stack[MAXN],bcc[MAXN];
int dfs_clock,top;
bool ok[MAXN];
int tmp[MAXN],cc;
int n,m;
int ans1,ans2;
struct Edge{
    int to,next;
}edge[MAXM<<1];int head[MAXN],tot;
void addedge(int u,int v){
    edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){
    tot=0;
    memset(head,0xff,sizeof(head));
}
void count(){
    int sum=0,u,v;
    for(int i=0;i<cc;++i){
        u=tmp[i];
        for(int j=head[u];j!=-1;j=edge[j].next){
            v=edge[j].to;
            if(ok[v]) sum++;
        }
    }
    sum/=2;
    if(sum>cc) ans2+=sum;
}
void dfs(int u,int pre){
    int v;
    low[u]=dfn[u]=++dfs_clock;
    Stack[top++]=u;
    for(int i=head[u];i!=-1;i=edge[i].next){
        v=edge[i].to;
        if(v==pre) continue;
        if(!dfn[v]){
            dfs(v,u);
            if(low[u]>low[v]) low[u]=low[v];
            if(low[v]>dfn[u]) ans1++;
            if(low[v]>=dfn[u]){
                cc=0;
                memset(ok,false,sizeof(ok));
                int vn;
                for(;;){
                    vn=Stack[--top];
                    tmp[cc++]=vn;
                    ok[vn]=true;
                    if(vn==v) break;
                }
                tmp[cc++]=u;
                ok[u]=true;
                count();
            }
        }
        else if(low[u]>dfn[v]) low[u]=dfn[v];
    }
}
void solve(){
    memset(dfn,0,sizeof(dfn));
    dfs_clock=top=0;
    ans1=ans2=0;
    for(int i=0;i<n;++i){
        if(!dfn[i]) dfs(i,-1);
    }
    printf("%d %d
",ans1,ans2);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.cpp","r",stdin);
#endif // ONLINE_JUDGE
    int u,v;
    while(scanf("%d%d",&n,&m)==2){
        if(n==0&&m==0) break;
        init();
        while(m--){
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        solve();
    }
    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 手写CrashHandler实现UncaughtExceptionHandler拦截android异常

下一篇 Android Instrumentation 简介

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点