文档章节

图论:双连通分支-点

o
 osc_1ee7cxmx
发布于 2018/08/06 21:28
字数 1330
阅读 0
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

POJ2942:利用Tarjan求无向图的点双连通分支

首先科普一下点双连通分支的求法:

貌似看起来繁琐而复杂。。

然而复杂的确实这道例题,暂时没有找到特别裸的。。

题干大意是这样的,开会,然后给出了一张图,边所连接的两个点互相憎恶,开会的时候只能奇数个人一起圆桌开,问T几个人会世界和平

做法的话,首先求原图的补图,然后求出补图的点双连通分量,对于每一个连通分量判断是否是二分图,如果不是二分图那么满足条件,如果是那就要T人了

这里的重点不是二分图判定,而是求点双连通分量的部分,二分图判定是在点双连通分量的基础上完成的

int n,m,cnt,deep,cnt1,ans,top,sum;
bool vis[maxn],vis1[maxn],vis2[maxn];
int g[maxn],dfn[maxn],low[maxn],tmp1[maxn],col[maxn],co[maxn],st[maxn];
int G[maxn][maxn];

图G是原图,邻接矩阵存储,既可以避免重边又可以方便建补图

然后cnt是边的数量,cnt1是临时存放的双连通分量中的点数,tmp1用来临时存放双连通分量,vis1用来判断点是否在双连通分量中

co是二分图染色数组,vis2是统计删点的

bool dfs(int u,int color)
{
    //cout<<"###"<<u<<" "<<color<<endl; 
    co[u]=color;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
    {
        int v=e[tmp].t;
        if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
        if(co[v]!=-1)
        {
            if(co[v]==color) return false;
            continue;
        }
        if(!dfs(v,!color)) return false;
    }
    return true;
}
bool dfs(int u,int color)
{
    //cout<<"###"<<u<<" "<<color<<endl; 
    co[u]=color;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
    {
        int v=e[tmp].t;
        if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
        if(co[v]!=-1)
        {
            if(co[v]==color) return false;
            continue;
        }
        if(!dfs(v,!color)) return false;
    }
    return true;
}

二分图DFS染色,代码风格不令人舒适

void tarjan(int u,int fa)
{
    //cout<<"###"<<u<<" "<<fa<<endl;
    low[u]=dfn[u]=++deep;
    vis[u]=1;
    st[++top]=u;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)
    {
        int v=e[tmp].t;
        if(v==fa) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                sum++;
                int vn;
                cnt1=0;
                memset(vis1,0,sizeof(vis1));  //用于判断点是否在当前连通分量里 
                do
                {
                    vn=st[top--];
                    col[vn]=sum;
                    vis1[vn]=1;
                    tmp1[cnt1++]=vn;  //临时存点双连通分量 
                    vis[vn]=0;
                }while(vn!=v);
                vis1[u]=1;
                memset(co,-1,sizeof(co));
                if(!dfs(u,0))  //对点双连通分量进行二分图判定 
                {
                    vis2[u]=1;  //是二分图,参与记录结果 
                    while(cnt1--) vis2[tmp1[cnt1]]=1;
                }
                //top--;
            }
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
}

Tarjan求点双连通分量+做文章,标记好了vis1之后,在处理的时候扫补图,然后特判一下,连通子图就出来了

下面给出完整的实现:

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int maxn=1005;
  6 const int maxm=1000005;
  7 int n,m,cnt,deep,cnt1,ans,top,sum;
  8 bool vis[maxn],vis1[maxn],vis2[maxn];
  9 int g[maxn],dfn[maxn],low[maxn],tmp1[maxn],col[maxn],co[maxn],st[maxn];
 10 int G[maxn][maxn];
 11 struct Edge{int t,next;}e[maxm];
 12 void addedge(int u,int v)
 13 {
 14     e[++cnt].t=v;e[cnt].next=g[u];
 15     g[u]=cnt;
 16 }
 17 bool dfs(int u,int color)
 18 {
 19     //cout<<"###"<<u<<" "<<color<<endl; 
 20     co[u]=color;
 21     for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
 22     {
 23         int v=e[tmp].t;
 24         if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
 25         if(co[v]!=-1)
 26         {
 27             if(co[v]==color) return false;
 28             continue;
 29         }
 30         if(!dfs(v,!color)) return false;
 31     }
 32     return true;
 33 } 
 34 void tarjan(int u,int fa)
 35 {
 36     //cout<<"###"<<u<<" "<<fa<<endl;
 37     low[u]=dfn[u]=++deep;
 38     vis[u]=1;
 39     st[++top]=u;
 40     for(int tmp=g[u];tmp;tmp=e[tmp].next)
 41     {
 42         int v=e[tmp].t;
 43         if(v==fa) continue;
 44         if(!dfn[v])
 45         {
 46             tarjan(v,u);
 47             low[u]=min(low[u],low[v]);
 48             if(low[v]>=dfn[u])
 49             {
 50                 sum++;
 51                 int vn;
 52                 cnt1=0;
 53                 memset(vis1,0,sizeof(vis1));  //用于判断点是否在当前连通分量里 
 54                 do
 55                 {
 56                     vn=st[top--];
 57                     col[vn]=sum;
 58                     vis1[vn]=1;
 59                     tmp1[cnt1++]=vn;  //临时存点双连通分量 
 60                     vis[vn]=0;
 61                 }while(vn!=v);
 62                 vis1[u]=1;
 63                 memset(co,-1,sizeof(co));
 64                 if(!dfs(u,0))  //对点双连通分量进行二分图判定 
 65                 {
 66                     vis2[u]=1;  //是二分图,参与记录结果 
 67                     while(cnt1--) vis2[tmp1[cnt1]]=1;
 68                 }
 69                 //top--;
 70             }
 71         }
 72         else if(vis[v]) low[u]=min(low[u],dfn[v]);
 73     }
 74 }
 75 void init()
 76 {
 77     cnt=deep=cnt1=top=sum=0;
 78     memset(vis,0,sizeof(vis));
 79     memset(vis1,0,sizeof(vis1));
 80     memset(vis2,0,sizeof(vis2));
 81     memset(g,0,sizeof(g));
 82     memset(dfn,0,sizeof(dfn));
 83     memset(low,0,sizeof(low));
 84     memset(tmp1,0,sizeof(tmp1));
 85     memset(col,0,sizeof(col));
 86     memset(co,0,sizeof(co));
 87     memset(st,0,sizeof(st));
 88     memset(G,0,sizeof(G));
 89     memset(e,0,sizeof(e));
 90 }
 91 int main()
 92 {
 93     int u,v;
 94     while(scanf("%d%d",&n,&m)==2)
 95     {
 96         init();
 97         if(n==0&&m==0) break;
 98         while(m--)
 99         {
100             scanf("%d%d",&u,&v);
101             G[u][v]=G[v][u]=1;
102         }
103         for(int i=1;i<=n;i++)
104             for(int j=1;j<=n;j++)
105                 if(i!=j&&G[i][j]==0) addedge(i,j);
106         for(int i=1;i<=n;i++)
107             if(!dfn[i]) tarjan(i,-1);
108         ans=n;
109         for(int i=1;i<=n;i++)
110             if(vis2[i]) ans--;
111         printf("%d\n",ans);
112     }
113     return 0;
114 }

讲道理这个题,综合性强,而且挺难的

 

上一篇: java--异常
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Kubernetes发布SpringBoot项目过程总结

SpringBoot 项目创建完成后,通常会打成 jar 包运行,如果不使用 Kubernetes 可以直接通过 java -jar 或者脚本启动,如果需要发布到 Kubernetes 环境,那么需要编写 Dockerfile、构建镜像、推...

strict_nerd
05/23
0
0
👉 最新推出【Jenkins扩展篇-API实践|监控】教程🎉🎉🎉 助力全方位Jenkins管理!课程详情可添加小助手微信: proc_code。

本文分享自微信公众号 - DevOps云学堂(idevopsvip)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

泽阳DevOps
02/18
0
0
没错,用三方 Github 做授权登录就是这么简单!(OAuth2.0实战)

本文收录在个人博客:www.chengxy-nds.top,技术资源共享。 上一篇《OAuth2.0 的四种授权方式》文末说过,后续要来一波OAuth2.0实战,耽误了几天今儿终于补上了。 最近在做自己的开源项目(f...

程序员内点事
7分钟前
9
0
Docker可视化工具Portainer

前言 对于新手来说,还是要熟悉并掌握Docker命令,因为它的命令还是非常清晰简单的。随着逐渐熟悉命令后,为了提高工作效率我们可以考虑借助一些工具协助。目前业界对于Docker可视化工具比较...

ville
11分钟前
19
0
从 Git 仓库的 Commit 历史中移除敏感文件

在很多情况,我们由于疏忽会将一些敏感信息误传到 Git 仓库上面去。 尽管我们可以使用git rm将包含敏感信息文件删除掉,然后重新提交上传,文件就不会在仓库文件列表显示。 但是这并不能完全...

A_laoshiren
16分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部