https://blog.csdn.net/WJPnb1/article/details/126332263?spm=1001.2014.3001.5501 第一次写csdn博客，写了这个找二分图最大匹配的，大家可以来看看，有问题交流交流

貌似开始把未染色值全初始化为0，一边染上色为任意值c，另一边则染成相反值-c更有利于新手理解，也不要来回想进一步是1还是2咯，hhh。

xdm，你们都用哪个版本啊，哪个版本更好啊

想知道为什么大佬的BFS用的好像是栈？是我判断错了吗？

不是用的队列吗，你说的是哪个

不好意思是我错了，我看到变量名就想成栈顶

hh

for(int i = 1; i <= n; i ++){
if(!st[i]){
if(!dfs(i, 1)){
flag = false;
break;
}
}
}
不是从1开始深搜就可以全部染色了吗？为什么还要遍历所有节点啊？

因为图 不一定联通，非连通图也可以 是 二分图

原来如此，懂了，阿里嘎多！

哦谢谢！

哪位大佬可以帮帮我，谢谢
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]

using namespace std;

const int N = 100010;

typedef pair[HTML_REMOVED] PII;

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

PII q[N * 2];

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

bool bfs(int u)
{
color[u] = 1;
q[0] = {u, 1};
int tt = 0, hh = 0;
while(hh <= tt)
{
auto t = q[hh ++];

    int x = t.first, y = t.second;

    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[x];
        if(!color[j]) 
        {
            q[++ tt] = {j, 3 - y};
            color[j] = 3 - y;
        }
        else if(color[j] == y) return false;
    }
}
return true;

}

int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while(m –)
{
int a, b;
cin >> a >> b;
if(a != b)
{
add(a, b);
add(b, a);
}
}

//我很好奇若出现重边和自环是怎么处理的？
bool flag = true;
for(int i = 1; i <= n; i ++)
{
    if(!color[i])//染过的连通块不需要再染一遍哦！！！
    {
        if(!bfs(i))
        {
            flag = false;
            break;
        }
    }
}
if(flag) puts("Yes");
else puts("No");
return 0;

}

自环就奇数环 就是false ；重2次边 涂2次 第一次涂上 第二次查看颜色对不对

orz

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

using namespace std;
const int N = 100010;
int idx,e[N],ne[N],h[N];
//e 是元素 ，ne 是下一条边 ， h 是起始边。 
int  tu[N];

typedef pair<int,int> INT;
//pair<int,int> 第一个是此点的颜色状态，第二个是此点的编号。 

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


bool bfs(int n){
    int hh=0,tt=0;
    INT q[N];
    q[0] = {1,n};
    tu[n] = 1;


    while(hh <= tt){
        INT t= q[hh++];
        int c=t.first,ver = t.second;


        for(int i=h[ver];i != -1 ; i = ne[i]){

            int j=e[i];

            if(!tu[j]){     //如果没有遍历过，就把这个点放进去， 

                tu[j]=3-c;
                q[++tt] = {3-c,j};

            }else if( tu[j] == c) return false; //如果遍历过就,判断是否相同，如果颜色相同就返回错误！ 
        }

    }

    return true;

}



int main(){
    int n,m;
    scanf("%d %d",&n,&m);

    memset(h,-1,sizeof h);

    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }


    int flag = true;
    for(int i=1;i<=n;i++){
        if(!tu[i]){
            if(!bfs(i)){
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");

    return 0;
}

能帮我看一下哪错了吗，超时了。

这里题目给的是无向图，如果有N条边，这需要2N长的数组来存；改为e[2N]，ne[2N]， 就好了

感谢大佬回复hh，我也更新一下题解，在代码注释里强调这个。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
unordered_map<int,vector<int>> mp;
int color[N]={0};
bool dfs(int x,int curColor){
    color[x]=curColor;
    for(auto& v:mp[x]){
        if(!color[v]){
            if(!dfs(v,3-curColor)) return false;
        }else{
            if(color[v]==curColor) return false;
        }
    }
    return true;
}
int main()
{
    int n,m,u,v;
    cin>>n>>m;
    while (m -- ){
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

#include<bits/stdc++.h> 用这个的话，会增加不少的运行时间，其他倒还好。
不过我有点好奇，int color[N]={0}; 和 直接int color[N]; 有区别么？为什么要赋值{0} 呢？

如果在intmian上面写直接默认0把，这样是多余的

所以如果队列要存pair类型的元素的话，只能手动模拟嘛qwq

可以调用容器0.0，可能是因为队列手动模拟比较简单，像红黑树，哈希表，这些我就没见过人硬写了（狗头）

也是可以用标准库里的queue，不过大家也是学基础课下来，在bfs就顺便可以练习一下手写队列hh。

需要改2处地方吧（下面附上完整代码）：
1. 加一下include
2. 然后改一下bfs函数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>  //  -----------> 加上 include

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
typedef pair<int, int> PII;

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

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

// --------------> 改一下bfs里之前队列的写法
bool bfs(int u){
    queue<PII> q;
    q.push({u, 1});
    st[u] = 1;

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int ver = t.first, c = t.second;

        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];

            if(!st[j])
            {
                st[j] = 3 - c;
                q.push({j, 3 - c});
            }
            else if(st[j] == c) return false;
        }
    }

    return true;
}

int main(){
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while(m --){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a); // 无向图
    }

    int flag = true;
    for(int i = 1; i <= n; i ++) {
        if (!st[i]){
            if(!bfs(i)){
                flag = false;
                break;
            }
        }
    }

    if (flag) puts("Yes");
    else puts("No");
    return 0;
}

十分感谢💞

牛逼 感谢

求大佬解答一下这句话： 无向图, 所以最大边数是2倍

因为是无向图是特殊的有向图 每一个点之间都互相连接着到彼此的两条边 所以最大是2倍

自己写的时候，就是这里忘了 T.T

大佬 bfs的时候 为什么要for啊，这样不是很多次bfs了吗？ 直接一次bfs（1） 然后while（不空） 不行吗

7 7
1 2
2 3
1 3
4 5
5 6
6 7
7 4
画图发现两个环，一次搜索遍历不了所有点

哦哦

写的很好

赞一个~

谢谢hh

大佬，请问能帮忙看下我这个bfs代码哪里有问题吗？感觉思路和你的差不多，我用的s数组存储颜色，起始都是-1，染色1或0。部分正确。。。

#include<iostream>
#include<string.h>
using namespace std;

const int N = 200010;
int e[N],ne[N],h[N];
int q[2 * N],s[N];
int n,m,idx;

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

bool bfs(int x)
{
  int hh = 1,tt = 1;

  q[hh] = x;
  s[x] = 1;

  while(hh <= tt)
  {
    for(int i = h[x];i != -1;i = ne[i])
    {
      int j = e[i]; 

      if(s[j] == -1) 
      {
       s[j] = !s[x];
       q[++tt] = j;
      }
      else if(s[j] == s[x]) return false;
    }
    hh++;
  }

  return true;
}

int main()
{
  scanf("%d%d",&n,&m);
  memset(h,-1,sizeof(h));
  memset(s,-1,sizeof(s));
  for(int i = 1;i <= m;i++)
  {
    int u,v;
    scanf("%d%d",&u,&v);

    add(u,v);
    add(v,u);
  }

  int flag = 1;
  for(int i = 1;i <= n;i++)
  {
    if(s[i] == -1 && !bfs(i))
    {
      flag = 0;
      break;
    }
  }

  if(flag) printf("Yes");
  else printf("No");

  return 0;
}

##### 有2个问题
1. add函数没写对，复习一下AcWing 826. 单链表，应该改成这样

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

2.bfs的模板也没对，模板是每次取队头，然后遍历队头所有的邻边，你这样写每次只会遍历了x这个点的邻边，根本不能遍历完整个图。。
我直接在你的代码基础上改（另外bfs的写法最好紧跟y总基础课 AcWing 844. 走迷宫的模板会清晰很多）。

bool bfs(int x)
{
  int hh = 1,tt = 1;
  q[hh] = x;
  s[x] = 1;

  while(hh <= tt)
  {
    x = q[hh ++]; // 加了这个就每次取的是队头的点编号
    for(int i = h[x];i != -1;i = ne[i])
    {
      int j = e[i]; 

      if(s[j] == -1) 
      {
       s[j] = !s[x];
       q[++tt] = j;
      }
      else if(s[j] == s[x]) return false;
    }
  }

  return true;
}

然后你直接把我上面改好的add函数和bfs函数替换之后就可以AC了~~

哦哦懂了，谢谢大佬！十分感谢！！！

不客气，互相学习hh

不对吧，add函数也可以这样写

哈喽，可以说一下是哪里不对吗？

其实只有第二个是改对了的

我是想知道，哪里不对，以及为什么不对，不太懂你意思。。

add可以写成

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

学死了

噢噢是可以，idx可以放前面++。上面确实评论错了。谢谢指出。

染色失败相当于至少存在2个 （相邻点）染了相同的颜色

好滴！已修正。严谨。

码风舒服

哈哈，是闫式风格