Как проверить, является ли граф двухцветным или нет?

Чтобы показать, что граф является двудольным, вам не нужен сложный алгоритм для проверки. Вы можете просто использовать раскрашивающую функцию DFS (поиск в глубину). Это может быть реализовано следующим образом:

int color[100005];              //I assume this is the largest input size, initialise all values to -1.
vector<int> AdjList[100005];    //Store the neighbours of each vertex
bool flag = true;               //Bipartite or Not Bipartite

void dfs(int x, int p){         //Current vertex, Parent Vertex
    if (!flag) return;
    if (p == -1) color[x] = 0;
    else color[x] = 1 - color[p];
    for (int i = 0; i < AdjList[x].size(); ++i){      //For Every Neighbour
        int v = AdjList[x][i];                        //Vertex to be checked
        if (color[v] == color[x]){                    //Same color -> Not bipartite
            flag = false;
            return;
        }      
        if (color[v] == -1){                           //Unchecked
            dfs(v,x);                                  //color
        }              
    }
}

Исходная проблема: https://www.codechef.com/problems/CHFNFRN

@Benson Lin Спасибо за такую ​​помощь.

Что ж, проблема с вашим ответом заключается в том, что он не работает, если граф отключен, то есть если он имеет 2 отключенных подграфа. Поскольку мы выбираем исходный узел случайным образом, приведенный выше код просто проверяет этот подграф с этим узлом и дает ответ только для подграфа, а не для графа. С небольшим изменением в приведенном выше коде мы можем решить эту проблему.

int colorArr[1001];

bool isBipartite(bool G[][1001], int src,int n)
{
colorArr[src] = 0;
queue <int> q;
q.push(src);
while (!q.empty())
{
    int u = q.front();
    q.pop();

     // Find all non-colored adjacent vertices
    for (int v = 0; v < n; ++v)
    {
        // An edge from u to v exists and destination v is not colored
        if (G[u][v]==true && colorArr[v] == -1)
        {
            // Assign alternate color to this adjacent v of u
            colorArr[v] = 1 - colorArr[u];
            q.push(v);
        }
         if(G[u][v]==true && colorArr[u]==colorArr[v] && u!=v)
                return false;

        //  An edge from u to v exists and destination v is colored with
        // same color as u
    }
}

// call the function with source node which is not color.
int count=0;
for(int i=0;i<n;i++)
{

        if(colorArr[i]==-1)
        {
            if(isBipartite(G,i,n))
            continue;
            else
                return false;
        }
    for(int j=0;j<n;j++)
    {
        if(G[i][j]==true )
        {
            if(colorArr[i]==colorArr[j] && colorArr[i]!=-1)
                return false;
        }

    }
}

return true;
 }

BFS можно использовать, раскрашивая чередующиеся уровни разными цветами и останавливаясь, если два узла одного цвета находятся рядом (не двудольные) или не обнаруживается такая несовместимая окраска (двудольный). Вот код Python (adj — это список смежности для входного графа, который нужно проверить):

def bipartite(adj):
    color = [None]*len(adj)
    for vertex in range(len(adj)):
        if not color[vertex]:
            queue = [vertex]
            color[vertex] = 'red'
            while len(queue) > 0:
                u = queue.pop(0)
                for v in adj[u]:
                    if color[v] ==  color[u]:
                        return 0
                    if not color[v]:
                        queue.append(v)
                        color[v] = 'red' if color[u] == 'blue' else 'blue'
    return 1

Следующая анимация показывает результат запуска bfs на заданном входном графе и раскраску графа в 2 цвета (также показана очередь bfs).