Определение двудольного графа с символьными узлами - PullRequest
Новая
       87

Определение двудольного графа с символьными узлами

0 голосов
/ 27 марта 2020

Я знаю этот код определения, является ли график двудольным или нет. Я пытался решить некоторые новые задачи и хочу определить, является ли граф с символьными узлами двудольными.

Вот изображение моего графика

Но я сталкиваюсь с некоторыми проблемами, я хочу принять данные от пользователя 1. Введите число ребер 2. Введите вершины, которые связаны друг с другом (как в AB, AD, DF), а затем Я хочу вывести, если это двудольный или нет. Какие изменения мне нужны в моем коде? Вот как я решил для целых узлов 

#include <bits/stdc++.h>
using namespace std;

const int V = 4;
bool isBipartiteUtil(int G[][V], int src, int colorArr[])
{
    colorArr[src] = 1;

    queue <int> q;
    q.push(src);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v = 0; v < V; ++v)
        {
            if (G[u][v] && colorArr[v] == -1)
            {
                colorArr[v] = 1 - colorArr[u];
                q.push(v);
            }

           else if (G[u][v] && colorArr[v] == colorArr[u])
                return false;
        }
    }

    return true;
}

bool isBipartite(int G[][V])
{
    int colorArr[V];
    for (int i = 0; i < V; ++i)
        colorArr[i] = -1;

    for (int i = 0; i < V; i++)
        if (colorArr[i] == -1)
            if (isBipartiteUtil(G, i, colorArr) == false)
                return false;

    return true;
}

int main()
{
    int G[][V] = {{0, 1, 0, 1},
                  {1, 0, 1, 0},
                  {0, 1, 0, 1},
                  {1, 0, 1, 0}
    };
    isBipartite(G) ? cout << "Yes" : cout << "No";
    return 0;
}

Кто-нибудь может мне помочь?

...