染色判断二分图

vector<int>a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
->a[]={1,2,3}

//bfs
#include<bits/stdc++.h>
const int maxn=1000;
using namespace std;
vector<int> G[maxn];  // 存边
int col[maxn];        // 标记顶点颜色
int n,m;         // 点和边的个数
bool bfs(){
  queue<int> q;
  q.push(1);     // 放入第一个点
  memset(col,0,sizeof(col));
  col[1] = 1;    // 先标记第一个点为1
  while(!q.empty()){
    int v = q.front();
    q.pop();
    for(int i=0;i<G[v].size();i++){
      int xx = G[v][i];
      if(col[xx] == 0){      // 判断这个点是否标记过
        col[xx] = -col[v];   // 没有标记过就标记上与v相反的颜色
        q.push(xx);
      }
      else{
        if(col[v] == col[xx]){    // 如果颜色冲突说明不是二分图
          return false;
        }
      }
    }
  }
  return true;
}
int main(){
    int n,m;
    int a,b;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if(bfs())cout<<"yes"<<endl;
    else cout<<"no"<<endl;
    return 0;
}

//dfs
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1005;
vector<int>G[maxn];
int color[maxn];
bool dfs(int u,int c){
    color[u]=c;
    for(int i=0;i<G[u].size();i++){
        if(color[G[u][i]]==c)return false;//相同色剪掉
        else if(color[G[u][i]]==0&&!dfs(G[u][i],-c))return false;
    }
    //都染色返回true
    return true;
}
int main(){
    int n,m;
    cin>>n>>m;
    memset(color,0,sizeof color);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int fl=0;
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){
                fl=1;
                break;
            }
        }
    }
    if(fl)cout<<"no"<<endl;
    else cout<<"yes"<<endl;
    return 0;
}