`
Coco_young
  • 浏览: 125784 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[双连通+割点+桥]无向图连通性问题专题

 
阅读更多

最近一直搞专辑，所以没写啥解题报告，今天终于搞完了一个，小结一下下

题目来源，LightOJ，在Problem Category里的Graph Theory里的Articulation/Bridge/Biconnected Component

1026 - Critical Links

裸题，找桥用tarjan算法即可解决

代码：

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 10010;
struct Brige{
    int u,v;
    Brige(){}
    Brige(int uu,int vv):u(uu),v(vv){}
    bool operator < (const Brige &b) const{
        if(u!=b.u)return u<b.u;
        else return v<b.v;
    }
};
vector<int> g[MAXN];
vector<Brige> brige;
int low[MAXN],dfn[MAXN],depth,n,t;
void init(){
    brige.clear();
    for(int i=0;i<MAXN;i++)g[i].clear();
    depth = 1;
    memset(dfn,-1,sizeof(dfn));
}
void tarjan(int fa,int u){
    low[u] = dfn[u] = depth++;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(dfn[v]==-1){
            tarjan(u,v);
            low[u] = min(low[u],low[v]);
            if(low[v]>dfn[u]){
                if(u<v){
                    brige.push_back(Brige(u,v));
                }else{
                    brige.push_back(Brige(v,u));
                }
            }
        }else if(v!=fa){
            low[u] = min(low[u],dfn[v]);
        }
    }
}
int main(){
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        printf("Case %d:\n",c);
        init();
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            int node,m;
            scanf("%d (%d)",&node,&m);
            for(int i=0;i<m;i++){
                int adj;
                scanf("%d",&adj);
                g[node].push_back(adj);
            }
        }
        for(int i=0;i<n;i++){
            if(dfn[i]==-1)tarjan(-1,i);
        }
        printf("%d critical links\n",brige.size());
        sort(brige.begin(),brige.end());
        for(int i=0;i<brige.size();i++){
            printf("%d - %d\n",brige[i].u,brige[i].v);
        }
    }
    return 0;
}


1063 - Ant Hills

求割点数，裸题，代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 10010;
vector<int> g[MAXN];
int low[MAXN],dfn[MAXN],cut[MAXN],tot,t,n,m,depth;
void init(){
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    depth = 1;tot = 0;
    for(int i=0;i<MAXN;i++)g[i].clear();
}
void tarjan(int fa,int u){
    low[u] = dfn[u] = depth++;
    int son = 0;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(!dfn[v]){
            tarjan(u,v);
            son++;
            low[u] = min(low[u],low[v]);
            if((u==1&&son>=2)||(u!=1&&dfn[u]<=low[v])){
                if(!cut[u])cut[u]=1,tot++;
            }
        }else if(v!=fa){
            low[u] = min(dfn[v],low[u]);
        }
    }
}
int main(){
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        init();
        scanf("%d%d",&n,&m);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
            //cout<<a<<" "<<b<<endl;
        }
        tarjan(-1,1);
        printf("Case %d: %d\n",c,tot);
    }
    return 0;
}


1291 - Real Life Traffic

求出所有的边双连通分量，即缩点，然后计算缩点以后图度数为1个结点的个数N，答案就是(N+1)/2，可以证明

不过简单的方法用一次tarjan就可以解决，代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 10010;
int low[MAXN],deg[MAXN],dfn[MAXN],t,n,m,depth,cnt;
vector<int> g[MAXN];
void init(){
    for(int i=0;i<MAXN;i++){
        g[i].clear();
    }
    memset(deg,0,sizeof(deg));
    memset(dfn,0,sizeof(dfn));
    depth = 1;cnt = 0;
}
void tarjan(int fa,int u){
    low[u] = dfn[u] = depth++;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(!dfn[v]){
            tarjan(u,v);
            low[u] = min(low[u],low[v]);
            if(low[v]>dfn[u]){//让值从子节点更新上来，根的信息已经无法继续更新，所以可以直接使用
                deg[v]++;
                deg[u]++;
                if(deg[v]==1)cnt++;
            }else{
                deg[u]+=deg[v];
            }
        }else if(v!=fa){
            deg[u]+=deg[v];
            low[u] = min(low[u],dfn[v]);
        }
    }
}
int main(){
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        init();
        scanf("%d%d",&n,&m);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        tarjan(-1,1);
        if(deg[1]==1)cnt++;
        printf("Case %d: %d\n",c,(cnt+1)/2);
    }
    return 0;
}


1300 - Odd Personality

此题有些蛋疼，题目是让求所有在奇圈上点的个数，其中奇圈中一个点可以出现多次，但是每一条边只能出现一次，咋一看很像POJ的Knight Of the Round Table,但是这里加了一个条件（一个点可使用多次），所以它不是在点双连通分量里面找奇圈，而是在边双连通分量里找奇圈（因为这个WA无数次，蛋碎），如何判断奇圈还是通过交叉染色法。

解题步骤：

1.用tarjan找出所有的边双连通分量

2.用交叉染色法对每一组边双连通分量进行交叉染色（染色失败即存在奇圈，那么该边双连通分量中的每一个点都在一个奇圈上，这条性质可以证明）

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 10010
#define MAXM 20010
vector<int> g[MAXN],gt[MAXN];
vector<int>::iterator ite;
int col[MAXN],good[MAXN],low[MAXN],dfn[MAXN],t,n,m,depth,flag;
void init(){
    memset(gt,0,sizeof(gt));
    memset(col,0,sizeof(col));
    memset(good,0,sizeof(good));
    memset(dfn,0,sizeof(dfn));
    for(int i=0;i<MAXN;i++)g[i].clear(),gt[i].clear();
    depth = 1;
}
void tarjan(int fa,int u){
    low[u] = dfn[u] = depth++;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(!dfn[v]){
            tarjan(u,v);
            low[u] = min(low[u],low[v]);
            if(low[v]>dfn[u]){
                for(ite=gt[u].begin();ite!=gt[u].end();ite++){
                    if(*ite==v){
                        gt[u].erase(ite);
                        break;
                    }
                }
                for(ite=gt[v].begin();ite!=gt[v].end();ite++){
                    if(*ite==u){
                        gt[v].erase(ite);
                        break;
                    }
                }
            }
        }else if(v!=fa&&dfn[v]<dfn[u]){
            low[u] = min(low[u],dfn[v]);
        }
    }
}
//交叉染色
void dfs_paint(int u,int c){
    col[u] = c;
    for(int i=0;i<(int)gt[u].size();i++){
        int v = gt[u][i];
            if(!col[v]){
                dfs_paint(v,-c);
            }else if(col[v]==col[u]){
                flag = 1;
            }
    }
}
//DFS标记answer
void dfs(int u){
    dfn[u] = good[u] = 1;
    for(int i=0;i<(int)gt[u].size();i++){
        int v = gt[u][i];
        if(!dfn[v])dfs(v);
    }
}
int main(){
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        init();
        scanf("%d%d",&n,&m);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
            gt[a].push_back(b);
            gt[b].push_back(a);
        }
        for(int i=0;i<n;i++)if(!dfn[i])tarjan(-1,i);
        memset(dfn,0,sizeof(dfn));
        for(int i=0;i<n;i++){
            if(!col[i]){
                flag = 0;
                dfs_paint(i,1);
                if(flag){
                    dfs(i);
                }
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            if(good[i])ans++;
        }
        printf("Case %d: %d\n",c,ans);
    }
    return 0;
}

1308 - Ant Network

此题也比较蛋碎，因为有一个特殊情况要处理，而且貌似需要用大数（个人比较挫，认为mod 2^64次方需要大数）

题目意思是：给定一个连通的无向图，在里面标记一些点，使得这个图在去除任意一个点后，所有的点和被标记的点是连通的，求出最少要标记多少个点，然后求出不同的方案数mod 2^64

其实可以发现，如果原图存在割点，那么只需要在每一个只含有一个割点的点双连通分量中把除割点以外的任意一个点标记即可，然后方案数就是所有这样的点双连通分量中结点个数-1的乘积（不含割点所以-1），然后有一个特殊情况。。。（这里蛋碎了），如果原图不存在割点，那么只需要标记两个点就可以了，方案数就是结点总数*（结点总数-1）/2。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;
/////////////////////////////////////
//big int
const int base = 10000;
const int width = 4;
const int N = 1000;
struct bint{
    int ln,v[N];
    bint(int r=0){
        for(ln = 0;r>0;r/=base)v[ln++] = r%base;
    }
    bint operator = (const bint &r){
        memcpy(this,&r,(r.ln+1)*sizeof(int));
        return *this;
    }
};
bool operator < (const bint &a,const bint &b){
    int i;
    if(a.ln!=b.ln)return a.ln<b.ln;
    for(i=a.ln-1;i>=0&&a.v[i]==b.v[i];i--);
    return i<0?0:a.v[i]<b.v[i];
}
bool operator <= (const bint& a,const bint& b){
    return !(b<a);
}
bint operator + (const bint &a, const bint &b){
    bint res;int i,cy=0;
    for(i=0;i<a.ln||i<b.ln||cy>0;i++){
        if(i<a.ln)cy+=a.v[i];
        if(i<b.ln)cy+=b.v[i];
        res.v[i] = cy%base; cy/=base;
    }
    res.ln = i;
    return res;
}
bint operator - (const bint &a,const bint &b){
    bint res;int i,cy=0;
    for(res.ln=a.ln,i=0;i<res.ln;i++){
        res.v[i] = a.v[i]-cy;
        if(i<b.ln)res.v[i]-=b.v[i];
        if(res.v[i]<0)cy=1,res.v[i]+=base;
        else cy = 0;
    }
    while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
    return res;
}
bint operator * (const bint &a,const bint &b){
    bint res;res.ln = 0;
    if(0==b.ln){res.v[0]=0;return res;}
    int i,j,cy;
    for(i=0;i<a.ln;i++){
        for(j=cy=0;j<b.ln||cy>0;j++,cy/=base){
            if(j<b.ln)cy+=a.v[i]*b.v[j];
            if(i+j<res.ln)cy+=res.v[i+j];
            if(i+j>=res.ln)res.v[res.ln++] = cy%base;
            else res.v[i+j] = cy%base;
        }
    }
    return res;
}
bint operator / (const bint &a,const bint &b){
    bint tmp,mod,res;
    int i,lf,rg,mid;
    mod.v[0] = mod.ln = 0;
    for(i=a.ln-1;i>=0;i--){
        mod = mod*base+a.v[i];
        for(lf=0,rg=base-1;lf<rg;){
            mid = (lf+rg+1)/2;
            if(b*mid<=mod)lf=mid;
            else rg = mid-1;
        }
        res.v[i] = lf;
        mod = mod-b*lf;
    }
    res.ln = a.ln;
    while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
    return res;
}
bint operator % (const bint &a,const bint &b){
    bint tmp,mod,res;
    int i,lf,rg,mid;
    mod.v[0] = mod.ln = 0;
    for(i=a.ln-1;i>=0;i--){
        mod = mod*base+a.v[i];
        for(lf=0,rg=base-1;lf<rg;){
            mid = (lf+rg+1)/2;
            if(b*mid<=mod)lf=mid;
            else rg = mid-1;
        }
        res.v[i] = lf;
        mod = mod-b*lf;
    }
    res.ln = a.ln;
    while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
    return mod;
}
int digits(bint &a){
    if(a.ln==0)return 0;
    int l = (a.ln-1)*4;
    for(int t=a.v[a.ln-1];t;++l,t/=10);
    return l;
}
bool read(bint &b,char buf[]){
    if(1!=scanf("%s",buf))return 0;
    int w,u,ln = strlen(buf);
    memset(&b,0,sizeof(bint));
    if('0'==buf[0]&&0==buf[1])return 1;
    for(w=1,u=0;ln;){
        u += (buf[--ln]-'0')*w;
        if(w*10==base){
            b.v[b.ln++] = u;
            u = 0;
            w = 1;
        }else{
            w *=10;
        }
    }
    if(w!=1)b.v[b.ln++]=u;
    return 1;
}
void write(const bint &v){
    int i;
    printf("%d",v.ln==0?0:v.v[v.ln-1]);
    for(i=v.ln-2;i>=0;i--){
        printf("%04d",v.v[i]);
    }
    printf("\n");
}
//////////////////////////////////////
const int MAXN = 10010;
vector<int> g[MAXN],bcc[MAXN];
stack< pair<int,int> > s;
int bcnt,depth,low[MAXN],dfn[MAXN],cut[MAXN],num[MAXN],belong[MAXN],t,n,m;
void init(){
    for(int i=0;i<MAXN;i++)g[i].clear(),bcc[i].clear();
    bcnt = 0;depth = 1;
    memset(cut,0,sizeof(cut));
    memset(dfn,0,sizeof(dfn));
    memset(belong,-1,sizeof(belong));
    memset(num,0,sizeof(num));
}
void tarjan(int fa,int u){
    low[u] = dfn[u] = depth++;int son = 0;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(!dfn[v]){
            son++;
            s.push(make_pair(u,v));
            tarjan(u,v);
            low[u] = min(low[u],low[v]);
            if((son>=2&&u==0)||(u!=0&&dfn[u]<=low[v]))cut[u]=1;
            if(dfn[u]<=low[v]){
                int fst=s.top().first,sec=s.top().second;
                while(dfn[fst]>=dfn[v]){
                    if(belong[fst]!=bcnt){
                        bcc[bcnt].push_back(fst);
                        belong[fst] = bcnt;
                    }
                    if(belong[sec]!=bcnt){
                        bcc[bcnt].push_back(sec);
                        belong[sec] = bcnt;
                    }
                    s.pop();
                    fst = s.top().first;sec = s.top().second;
                }
                s.pop();
                if(belong[u]!=bcnt){
                    belong[u] = bcnt;
                    bcc[bcnt].push_back(u);
                }
                if(belong[v]!=bcnt){
                    belong[v] = bcnt;
                    bcc[bcnt].push_back(v);
                }
                bcnt++;
            }
        }else if(v!=fa&&dfn[v]<dfn[u]){
            s.push(make_pair(u,v));
            low[u] = min(low[u],dfn[v]);
        }
    }
}
void make_num(){
    for(int i=0;i<bcnt;i++){
        for(int j=0;j<(int)bcc[i].size();j++){
            if(cut[bcc[i][j]])num[i]++;
        }
    }
}
bint pow2(int p){
    if(p==0)return 1;
    bint a = pow2(p/2);
    if(p%2)return a*a*2;
    else return a*a;
}
void solve(int c){
    bint mul = 1;
    bint mod = pow2(64);
    int ans = 0;
    for(int i=0;i<bcnt;i++){
        if(num[i]==1){
            ans++;
            mul = (mul*(bcc[i].size()-1))%mod;
        }
    }
    printf("Case %d: %d ",c,ans);if(ans)write(mul);else printf("0\n");
}
int main(){
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        init();scanf("%d%d",&n,&m);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        tarjan(-1,0);
        if(bcnt!=1){
            make_num();
            solve(c);
        }else{//原始图就是双连通时要特殊处理
            printf("Case %d: %d %d\n",c,2,n*(n-1)/2);
        }
    }
    return 0;
}




分享到：
| [动态规划]HDU_1024_MaxSum Plus Plus
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    点割集、边割集、割点、桥、连通度、双连通分支定义1

    在图论中，无向图G是由顶点集V和边集E组成的数学结构，用于描述对象之间的连接关系。在图的分析中，点割集、边割集、割点、桥、连通度和双连通分支是关键概念，它们帮助我们理解图的结构特性。 1. **点割集**： 点...

    无向图的连通性

    图文并茂地介绍了割点，桥，双连通子图，双连通分支，最近公共祖先（LCA）， 其中穿插着例题与习题，每个知识点均有模板。

    图论- 图的连通性.rar

    割点与桥类似，也是影响图连通性的重要因素。 六、应用 图的连通性在计算机科学和网络设计中有着广泛的应用，如路由算法、社交网络分析、电路设计、数据结构设计（如树形结构）、网络流问题等。理解和掌握图的连通...

    图论中的连通性问题2.111111

    连通性问题的研究可以分为无向图和有向图两大类。在无向图中，我们可以使用深度优先搜索（Depth-First Search，DFS）来遍历所有的顶点和边。深度优先搜索是一种遍历图的方法，它从一个顶点开始，沿着边遍历图，直到...

    锦绣育才图的连通性PPT

    - **无向图的连通性** - **定义**: 若在无向图中任意两点间都有路径，则称该图为连通的。 - **非连通图**: 一个非连通图可以被划分为若干个互不相连的连通分量。 - **有向图的强连通性** - **定义**: 若在有向图...

    离散数学图连通性PPT课件.pptx

    "离散数学图连通性PPT课件" 本资源是一个关于离散数学图连通性的PPT课件，总共28页，涵盖了图的连通性、通路与回路、连通图、点割集与边割集等重要概念。 图的连通性 图的连通性是指图中的顶点之间是否存在路径。...

    图的连通_黄哲威.pdf

    在无向图中，可以通过删除节点或边来判断是否为割点或桥，而有向图的判断需要额外考虑反向边。 对于题目中的应用，例如"受欢迎的牛"问题，可以通过构建有向图并应用Tarjan算法求得强连通分量。如果缩点后有出度为0...

    无向图中的桥_C语言_codeblock.zip

    无向图中的桥是图论中的一个重要概念，它在数据结构和算法分析中具有广泛的应用。在这个项目中，我们使用C语言和CodeBlocks IDE来实现一个程序，该程序能够识别并找出无向图中的桥。 首先，理解无向图中的桥（Cut ...

    图论算法 最短路径 最小生成树 连通性 支配集 A*算法

    若图中存在割点（删除该节点会导致图不连通），则割点检测也是连通性研究的一部分。 4. **支配集**：在无向图中，支配集是一个节点子集，其中每个节点要么在子集中，要么与子集中的某个节点相邻。求解最小支配集...

    无向图缩点：tarjan点双与边双缩点(模板)

    无向图缩点是图论中的一个重要概念，用于简化图的结构，特别是在处理强连通分量或查找桥（割点）时非常有用。这里提到的"tarjan点双与边双缩点"是一种基于Tarjan算法实现的无向图缩点方法。Tarjan算法是一个用于查找...

    改造成双连通图2

    例如，如果图是有向无环图(DAG)，可能需要找到一条最小生成树(Minimum Spanning Tree, MST)来添加新边，以保持低的总体成本。 在输出结果时，通常会展示改造后的图结构，包括新的边以及验证图是否真的成为双连通图...

    图与遍历算法

    图论是研究图的数学分支，包含无向图、有向图、树和二叉树、赋权图以及网络等概念。 无向图是图论的基础，它的边没有方向，可以连接任意两个顶点。无向图的度是某个顶点所连接的边的数量。例如，如果一个顶点有三条...

    POJ1523 SPF【割点】

    割点，也称为关键顶点，是指在无向图中，如果移除该顶点及其所有相邻边，会导致图中至少有两个连通分量，即原图会断开成两个或更多个不相交的部分。 【描述】"POJ1523-SPF 【割点】 解题报告+AC代码+测试数据"表示...

    图论中的圈与块，无向图的最小环

    割边则是在无向图中，如果删除这条边，会导致原本连通的两个顶点变为不连通。这两种概念常用于分析图的结构稳定性，特别是在网络设计和容错系统中。 2. **最小生成树**（MST）：MST是无向加权图中边的子集，它包含...

    图论模板详细

    - 无向图求割点与桥：割点是无向图中去掉该点（以及与它相连的边）后，会导致原图不连通的点；桥是指去掉后会导致原图不连通的边。 - 无向图边双连通分量：在无向图中，若删除任一边都不会导致图不连通，则称该边...

    C算法 V（第二卷 图算法

    割点是指删除该顶点后会使得无向图的连通性改变的点，桥是指删除某条边之后会使得无向图的连通性改变的边。环是指在图中经过一系列顶点后，最终又回到起始顶点的路径，且路径上的边不重复。 由于该书是通过OCR扫描...

    离散数学图论习题课PPT学习教案.pptx

    点割集、割点和边割集（桥）用于分析图的连通性，它们在删除后会导致图变为不连通。节点的连通度k(G)和边的连通度λ(G)分别表示最小点割集和最小边割集的大小。 3. **图的矩阵表示**：无向图的邻接矩阵记录了节点间...

    图论图的基本概念PPT教案.pptx

    此外，图的连通性是无向图的重要特性，无向图的连通分支指的是图中任意两个节点间都存在路径的子图。点割集、割点、边割集和割边等相关概念用于分析图的连通性，它们在网络流、最短路径等问题中有广泛应用。有向图的...

    怎么采用C语言的程序编写的过程实现序列的删除

    这个问题是关于图论和算法设计的一个经典实例，具体而言，涉及的是无向图的边删除问题，要求在满足特定条件的情况下删除最少的边。我们来深入解析这个问题。 首先，问题描述了一个无向图 G，它有 n 个顶点和 m 条边...

Magicbox
Global site tag (gtag.js) - Google Analytics