bipartido.cpp

#include <bits/stdc++.h>
 
using namespace std;
const int maxn = 110;
vector<int> grafo[maxn];
int cor[maxn];
 
void bfs(int l){
    cor[l] = 0;
    queue<int> fila;
    fila.push(l);
    while(!fila.empty()){
        int u=fila.front();
        fila.pop();
        
        for(auto v : grafo[u]){
            if(cor[v] == -1){
                cor[v] = !cor[u];
                fila.push(v);
            }
        }
    }
}
 
bool bipartido(int n){
    for(int i=1;i<=n;i++){
        if(cor[i] == -1)
            bfs(i);
    }
    for(int u=1;u<=n;u++){
        for(auto v : grafo[u]){
            if(cor[v] == cor[u]) return false;
        }
    }
    return true;
}
 
int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    int k=0;

    for(int i=1;i<=m;i++){
        int a, b;
        cin >> a >> b;
        grafo[a].push_back(b);
        grafo[b].push_back(a);
    }
    
   	if(bipartido(n)) cout << "sim\n";
   	else cout << "nao\n";
    
    
    
    return 0;
}