首页 > 其他分享 >从CF1702E看二分图判断的两种方法

从CF1702E看二分图判断的两种方法

时间:2024-03-12 21:23:28浏览次数:26  
标签:二分 std 判断 ok int CF1702E dsu ++ edge

https://www.luogu.com.cn/problem/CF1702E

转化题意

把所有数连边,判断是否为二分图。

染色法

void solve() {
    #define tests
    int n;
    std::cin >> n;
    std::map<int, std::vector<int>> edge;
    std::vector<bool> used(n + 1);
    bool ok(true);
    for (int i = 0; i < n; i++) {
        int a, b;
        std::cin >> a >> b;
        edge[a].push_back(b); 
        edge[b].push_back(a);
        if (a == b or sz(edge[a]) > 2 or sz(edge[b]) > 2) {ok = false;}//出现次数大于二
    }

    if (not ok) {NO; return ;}

    auto dfs = [&](auto self, int now) -> int {
        used[now] = true;
        for (auto to : edge[now]) if (not used[to]) {
            return self(self, to) + 1;
        }
        return 1;
    };//其实也是判断有没有奇环,显然总数加起来如果是奇数就是奇环

    for (int i = 0; i < n; i++) {
        if (not used[i + 1] and (dfs(dfs, i + 1) & 1)) {
            ok = false;
        }
    }
    ok ? YES : NO;
}

扩展域并查集

//扩展域并查集维护是否为二分图
//构造出x的敌人x+n和y的敌人y+n
//因为是分成两个集合,所以只要构造一个敌人(即另一个与自己相等的数,但不能放到同一个集合内所以称为敌人)
//把x和y的敌人合并,y和x的敌人合并
//如果x和自己的敌人在一个并查集,就不合法

void solve() {
    #define tests
    int n;
    std::cin >> n;
    std::vector<int> cnt(n);
    DSU dsu(n * 2);
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;
        cnt[x]++; cnt[y]++;
        dsu.merge(x, y + n); dsu.merge(x + n, y);
    }
    bool ok(true);
    for (int i = 0; i < n; i++) {
        if (cnt[i] > 2) ok = false;
        if (dsu.find(i) == dsu.find(i + n)) ok = false;
    }
    ok ? YES : NO;
}

标签:二分,std,判断,ok,int,CF1702E,dsu,++,edge
From: https://www.cnblogs.com/kdlyh/p/18069306

相关文章

  • react 判断img加载完成
     react判断img加载完成在React中,可以通过监听img元素的load事件来判断图片是否加载完成。以下是一个简单的例子:  importReact,{useState,useRef}from'react'; constImageLoader=()=>{const[imageLoaded,setImageLoaded]=useState(false)......
  • 从CF1730B看题意转化与二分三分
    Problem-1730B-Codeforces贪心解法\(∣a−b∣=\max(a−b,b−a)\)由绝对值的性质易证。那么直接把\(t_i\)算到距离中,转换成求最左和最右“坐标”的中间点的简单问题。//通过把t[i]算到距离中,转换成求最左和最右坐标的中间点的简单情况voidsolve(){#definete......
  • 取反(分块+二分)
    第2题   取反 查看测评数据信息给一个长度是n的数组,a[1],a[2],a[3],...a[n-1],a[n],初始时a数组中所有的元素都为0,下面有两种操作:1.指定一个区间[x,y],把a[x],a[x+1],...a[y]的值取反,即如果a[i]的值为1则把a[i]的值变为0,如果a[i]的值为0则把a[i]的值变为12.指定一个区......
  • 统计数量(分块+二分)
    第1题   统计数量 查看测评数据信息给一个长度是n的正整数数组,a[1],a[2],a[3],...a[n-1],a[n],其中1<=a[i]<=1000。现在在数组a上进行m次操作:1.Mxyz,表示对a数组的闭区间[x,y]内所有a[i]的值分别加上z2.Axyzz,询问a数组闭区间[x,y]内有多少a[i]的值大于等于z......
  • Python 列表中任意字符串是否存在的判断
    `importsysjudge_string=[]target_string=sys.argvjudge_string=['-?','/?','--?','-help','--help','help']target_string=sys.argvjudge_result=any(wordifwordintarget_stringelseFals......
  • 上传文件附件时判断word、excel、txt等是否含有敏感词如身份证号,手机号等
    上传附件判断word、excel、txt等文档中是否含有敏感词如身份证号,手机号等,其它检测如PDF,图片(OCR)等可以自行扩展。互联网项目中,展示的数据中不能包含个人信息等敏感信息。判断word中是否包含手机号,word正文中是否包含身份证号等敏感信息,通过正则表达式判断匹配手机号,身份证号,以下做......
  • c# 判断图片、pdf是A0、A1、A2、A3、A4
    //("A0841*1189(mm)999949");//("A1594*841(mm)499554");//("A2420*594(mm)249485");//("A3297*420(mm)124740");//("A4210*297(mm)62370");//("B3353*500(mm)176500");//("B4250*353(mm)8825......
  • Java的结构、equals字符串判断与反编译
    顺序结构Java的基本结构就是顺序结构,除非特别指明,否则就按照顺序一句一句往下执行顺序结构是最简单的算法结构语句与语句之间,框与框之间是按上到下的顺序进行的,它是由若干个依次执行的处理步骤组成的,它是任何一个算法都离不开的一种基本算法结构代码举例publicclas......
  • C语言判断表达式的写法3<keyDown && keyDown<14
    if(3<keyDown&&keyDown<14){//Yourcodehere}可以写成if(3<keyDown<14){//Yourcodehere}吗答案:不能,因为在C语言中,if(3<keyDown&&keyDown<14) 和 if(3<keyDown<14) 是不同的。在C语言中,3<keyDown......
  • POJ--3258 River Hopscotch(二分搜索/最大化最小值)
    记录10:232023-3-11http://poj.org/problem?id=3259二分法查找最大的可能解,检查x是否符合条件(当前这个位置上的值-前上一个选取位置的值>=x)注意的点:使用了[begin,end)的左闭右开区间,所以结果要begin-1,end要从L+1开始算点击查看代码intL,N,M;introcks[5......