文档章节

【DFS】CODE[VS] 1535 封锁阳光大学(二分图DFS染色)

Fograin
 Fograin
发布于 2016/11/02 12:26
字数 1237
阅读 23
收藏 0

点击进入异世界


这个题,题意是给图染色判断是否为二分图
什么事二分图呢
顾名思义是可以将一个图中的点分为两个集合的图

这道题既可以用DFS也可以用BFS,先写下DFS的做法(比我写的BFS快一些)

二分图满足一个性质:不存在拥有奇数条边的环。如果存在则不是二分图因为,在二分图定义中,同属一个集合的点互相之间是没有连边的,若存在奇数环,则说明同集合点一定有连边。

如下图所示:

当有环且环上边数为偶数时
同集合点是没有连边的,也就是说一条边的两端点一定所属集合不同
这里写图片描述

当有环且环上边数为奇数时
左边点集中有两点连边,该边的两端点所属集合相同
这里写图片描述

二分图染色,就是将一个图按照二分图的规则对图中的点进行划分,若可以完成染色则说明该图是二分图


回到题目,题目实际上就是让我们进行二分图染色看是不是二分图
定义sum[1]是“黑色”,sum[2]是“白色”,在搜索每个连通子图(数据可能有的子图互相之间不连通)的时候,初始化搜索的第一个点为sum[1];

开始枚举,如果这个点没有遍历到则取与他父节点相反的颜色
若这个图遍历过,则判断其与其父节点的颜色是否相同,若相同则输出“Impossible”

这个题打了好几份代码,只有一份能AC,其余的都50分,这里附上两份


第一个打傻了的DFS+Trajan(50分)
当时混淆了双连通和连通,然后就没有与然后了….居然还能过5个点orz(垃圾代码,注释懒得删了)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

const int maxn = 120100;

using namespace std;

int tot;
int n,m;
int ans;
int qlt[maxn];
int head[maxn];
int color[maxn];
bool motherfucker;
bool vis[maxn];


struct node{
    int f,t,next;
}e[maxn << 1];

inline void build(int x,int y)
{
    //cout<<"------------------------------------"<<endl;
    tot++;
    //cout<<"head_after of "<<x<<" : "<<head[x]<<endl; 
    e[tot].f = x;
    e[tot].t = y;
    //cout<<tot<<" to : "<<e[tot].t<<endl;
    e[tot].next = head[x];
    //cout<<tot<<" next : "<<e[tot].next<<endl;
    head[x] = tot;
    //cout<<"head_fin of "<<x<<" : "<<head[x]<<endl; 
    //cout<<"------------------------------------"<<endl;
}

inline void dfs(int w,int muy1)
{
    //cout<<"当前的w为"<<w<<"muy1为"<<muy1<<endl; 
    //cout<<"ans_after: "<<ans<<endl; 
    //cout<<"color of "<<w<<" is "<<color[w]<<endl; 
    //cout<<"motherfucker: "<<motherfucker<<endl;
    ans = max(ans , muy1);
    //cout<<"ans_fin: "<<ans<<endl;
    //cout<<"head of "<<w<<" is "<<head[w]<<endl;
    for(int i = head[w];i;i = e[i].next)
    {
        //cout<<"i----> "<<i<<endl;
        //cout<<"colorw of "<<w<<" : "<<color[w]<<endl;
        //cout<<"color of "<<e[i].t<<" : "<<color[e[i].t]<<endl;
        int cmuy = muy1;
        if(color[e[i].t] == 0)
        {
            if(color[w] == 1&&vis[e[i].t] != 1)
                color[e[i].t] = 2;
            if(color[w] == 2&&vis[e[i].t] != 1)
            {
                muy1++;
                color[e[i].t] = 1;
            }
            dfs(e[i].t,muy1);
            muy1 = cmuy;
        }
        else if(color[w] == color[e[i].t])
        {
            //cout<<color[w]<<" "<<color[e[i].t]<<endl;
            motherfucker = 1;
            //cout<<"now of motherfucker : "<<motherfucker<<endl;
        }
    }
}

int lowlink[maxn],sccno[maxn],clockw,cnt;

stack<int >s;

void tj(int u)
{
    cout<<u<<endl;
    qlt[u] = lowlink[u] = ++clockw;
    cout<<"lowlink of "<<u<<" "<<lowlink[u]<<endl;
    s.push(u);
    cout<<"stack : "<<s.top()<<endl;
    for(int i = head[u];i;i = e[i].next)
    {
        int v = e[i].t;
        if(!qlt[v])
        {
            tj(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u] = min(lowlink[u],qlt[v]);
        }
    } 
    if(lowlink[u] == qlt[u])
    {
        cnt++;
        for(;;)
        {
            int x = s.top();
            s.pop();
            sccno[x] = cnt;
            if(x == u||s.empty())
                break;
        }
    }
}

void find_scc(int xx)
{
    clockw = cnt = 0;
    memset(sccno,0,sizeof(sccno));
    memset(qlt,0,sizeof(qlt));
    for(int i = 1;i <= xx;i++)
    {
        if(!qlt[i])
            tj(i);
    }
}

bool cntused[maxn];

int main()
{
    memset(color,0,sizeof(color));
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int aa,bb;
        scanf("%d%d",&aa,&bb);
        build(aa,bb);
        build(bb,aa);
    }
    vis[1] = 1;
    color[1] = 1;
    find_scc(n);
    for(int i = 1;i <= n;i++)
    {
        if(cntused[sccno[i]] == 0)
        {
            cntused[sccno[i]] = 1;
            dfs(i,1);
        }
        if(cntused[sccno[i]] == 1)
            continue;
    }
    if(motherfucker == 1)
        printf("Impossible\n");
    //cout<<"fuckyou"<<endl;
    if(motherfucker == 0)
    {
        int dc = n-ans; 
        if(ans > dc)
        {
            for(int i = 1;i <= n;i++)
            {
                if(head[i] == 0)
                    dc++;
            }
            printf("%d\n",dc);
        }
        else
        {
            for(int i = 1;i <= n;i++)
            {
                if(head[i] == 0)
                    ans++;
            }
            printf("%d\n",ans);
        }

    }
return 0;
}

第二份是”极为正常”的DFS,要从1for到n,如果这个点没到过,就DFS递归调用

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int maxn = 10010;

using namespace std;

int tot;
int ans;
int n,m;
int color[maxn];
int head[maxn];
int sum[3];
bool vis[maxn];

struct node{
    int f;
    int t;
    int next;
}e[maxn << 1];

inline void build(int ff,int tt)
{
    tot++;
    e[tot].f = ff;
    e[tot].t = tt;
    e[tot].next = head[ff];
    head[ff] = tot;
}

inline bool dfs(int x,int cnt)
{
    vis[x] = 1;
    color[x] = cnt;
    sum[cnt]++;
    for(int i = head[x];i;i = e[i].next)
    {
        int u = e[i].t;
        if(vis[u] == 1)
        {
            if(color[x] == color[u])
                return false;
        }
        else 
        {
            if(color[x] == 1)
                dfs(u,2);
            if(color[x] == 2)
                dfs(u,1);
        }
    }
return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        build(a,b);
        build(b,a);
    }
    for(int i = 1;i <=n;i++)
    {
        sum[1] = sum[2] = 0;
        if(vis[i] == 0)
        {

            if(dfs(i,1) == false)
            {
                printf("Impossible\n");
                return 0;
            }
            ans += min(sum[1],sum[2]);
        }
    }
    printf("%d\n",ans);
return 0;
}

THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog

© 著作权归作者所有

Fograin
粉丝 0
博文 22
码字总数 16052
作品 0
莱芜
程序员
私信 提问
洛谷 P1330 封锁阳光大学 【思维 + 二分图判定】

版权声明:本文为博主原创文章,喜欢就点个赞吧 https://blog.csdn.net/Anxdada/article/details/82627917 传送门 题意: 可以占领一点, 然后和这个点相邻的边都被封锁了, 如果在占领的这一点...

Anxdada
2018/09/11
0
0
Codeforces 题目合集+分类+蒟蒻的代码 【Updating...】【167 in total】

894A - QAQ 暴力 http://paste.ubuntu.com/26011561/ 894B - Ralph And His Magic Field 数学 http://paste.ubuntu.com/26011566/ 894C - Marco and GCD Sequence 构造 http://paste.ubuntu.......

my_sunshine26
2017/07/29
0
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0
[HAOI2017] 新型城市化

给出的图中恰包含2个团,则图的补图为一个二分图,其最大独立集为原图的最大团。 我们知道,二分图的最大独立集=V-最小顶点覆盖,最小顶点覆盖=最大匹配。 问题转化为:计算删去后最大匹配减...

nosta
2018/12/24
0
0
2018年12月份冬季PAT甲级考试总结

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/84931516 终于从威海回到学校了,可以平复一下想打死自己的心情写一下总结了。 本来打算这...

语海与冰
2018/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

二、Docker

1、Docker - The TLDR(Too Long,Don't Read,Linxu 终端工具 ) Docker是在Linux和Windows上运行的软件。它创建、管理和编排容器。该软件以开源方式开发,在Github上作为Moby开源项目的一部分。...

倪伟伟
24分钟前
2
0
Python猫荐书系列之七:Python入门书籍有哪些?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/ArN-6mLPzPT8Zoq0Na_tsg 最近,猫哥的 Python 技术学习群里进来了几位比较特殊的同学:一...

豌豆花下猫
今天
5
0
Guava RateLimiter限流源码解析和实例应用

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存 缓存的目的是提升系统访问速度和增大系统处理容量 降级 降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高...

算法之名
今天
13
0
国产达梦数据库与MySQL的区别

背景 由于项目上的需要,把项目实现国产化,把底层的MySQL数据库替换为国产的达梦数据库,花了一周的时间研究了国产的数据库-达梦数据库,它和MySQL有一定的区别,SQL的写法也有一些区别。 ...

TSMYK
今天
2
0
老也有错?35岁程序员是一道坎,横亘在每个技术职场人的心中

随着互联网的高速发展变革,大龄恐惧症越来越多地在技术圈被人讨论。很多程序员在工作5-10年以后,都会开始思考5年、10年甚至更久以后的自己,会是怎样一种生活工作状态,以及是否会被时代抛...

我最喜欢三大框架
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部