首页 > 其他分享 >AcWing 860. 染色法判定二分图

AcWing 860. 染色法判定二分图

时间:2023-08-18 20:32:21浏览次数:47  
标签:二分 idx int 860 ne dfs color 染色法 AcWing

JWvFczgRNg.jpg

题目

给定一个 $n$ 个点 $m$ 条边的无向图,图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式 第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行,每行包含两个整数 $u$ 和 $v$,表示点 $u$ 和点 $v$ 之间存在一条边。

输出格式 如果给定图是二分图,则输出 Yes,否则输出 No

数据范围 $1≤n,m≤10^5$ 输入样例:

4 4
1 3
1 4
2 3
2 4

输出样例:

Yes

思路

二分图:可以把所有点分成两个集合,边不在集合中 二分图不含奇数环

算法思路:

for i in 1~n
    if !color[i]
        dfs(i, 1)

代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c)
{
    color[u] = c;
    
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }
    
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        
        add(a, b);
        add(b, a);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }
    
    if (flag) puts("Yes");
    else puts("No");
    
    return 0;
}

标签:二分,idx,int,860,ne,dfs,color,染色法,AcWing
From: https://blog.51cto.com/u_16170343/7141213

相关文章

  • CF 1860 VP
    A猜结论,谁都会!B简单数学,谁都会!C简单博弈,谁都会!D数据范围小,\(O(N^4)\)乘小常数可以过。\(00,10,01,11\)个数均知道。\(i\)是\(1\)导致\(01,11\)总和增加\(i\)。dp即可。E要么不传送。要么\(x\)到一个地方,传送到一个地方,再到\(y\)。预处理所有可能的......
  • AcWing 858. Prim算法求最小生成树
    题目给定一个$n$个点$m$条边的无向图,图中可能存在重边和自环,边权可能为负数。求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。给定一张边带权的无向图$G=(V,E)$,其中$V$表示图中点的集合,$E$表示图中边的集合,$n=|V|,m=|E|$。由$V$中的全部$n$个......
  • AcWing 854. Floyd求最短路
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。再给定$k$个询问,每个询问包含两个整数$x$和$y$,表示查询从点$x$到点$y$的最短距离,如果路径不存在,则输出impossible。数据保证图中不存在负权回路。输入格式第一行包含三个整数$n,m,k......
  • AcWing 852. spfa判断负环
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。请你判断图中是否存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$,表示存在一条从点$x$到点$y$的有向边,边长为$z$。输出格式如果图中存在负......
  • Acwing第116场周赛
    Acwing.第116场周赛这次做的稍微通畅一点,但是做到第三题还是发懒了,以后每次周赛打完都会有一个周赛总结第一题:简单判断给定三个非负整数x,y,z,请根据如下要求进行判断并输出结果:如果x>y+z,输出+;如果y>x+z,输出-;如果x=y并且z=0,则输出0;如果以上都不满足,则输出?......
  • AcWing116
    AcWing116AAcWing5134.简单判断voidsolve(){intx,y,z;cin>>x>>y>>z;if(x>y+z)cout<<'+'<<endl;elseif(y>x+z)cout<<'-'<<endl;elseif(x==......
  • AcWing 851. spfa求最短路
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。请你求出$1$号点到$n$号点的最短距离,如果无法从$1$号点走到$n$号点,则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整......
  • acwing 116.飞行员兄弟 (算法竞赛进阶指南 p48 t1 ) 题解
    原题链接https://www.acwing.com/problem/content/description/118/题目描述“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。已知每个把手可以处于以下两种状态之一:打开或关闭。只有当所有把手都打开时,冰箱才会打开。把手可以表示为一个4х4的矩阵,您可以......
  • AcWing 850. Dijkstra求最短路 II
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,所有边权均为非负值。请你求出$1$号点到$n$号点的最短距离,如果无法从$1$号点走到$n$号点,则输出$−1$。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$,表示存在一条从点$......
  • Acwing 849. Dijkstra求最短路 I
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出$1$号点到$n$号点的最短距离,如果无法从$1$号点走到$n$号点,则输出$−1$。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$,表示存在一条从点$x$......