Проверка графа, заданного матрицей смежности, на двудольность

#include <iostream>
using namespace std;
#define N 100
int main ()
{   
    int a[N][N], i, q[N], b[N]={0}, i_st, i_end, n;
    bool fl=true;
    cout<<"kol-vo vershin:  ";
    cin>>n;
    // здесь делаете заполнение графа смежности нулями и единицами (0 - нет пути, 1 - есть пусть)
    while(true)
    {
        for(i=0; i<n; i++)
            if(b[i]==0)
            {
                b[i]=1;
                q[0]=i;
                break;
            }
        if(i==n)
            break;
        i_st=0; i_end=1;
        while(i_st<i_end)
        {
            for(i=0; i<n; i++)
                if(a[q[i_st]][i] && q[i_st]!=i)
                {
                    if(b[i]==0)
                    {
                        q[i_end++]=i;
                        if(b[q[i_st]]==1)
                            b[i]=2;
                        else
                            b[i]=1;
                    }
                    else
                    {
                        if(b[q[i_st]]==b[i])
                            fl=false;                   
                    }
                }
            i_st++;
        }
    }
    if(fl) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

#include <iostream>
using namespace std;
#define N 100
int main ()
{   
    int a[N][N], i, q[N], b[N]={0}, i_st, i_end, n;
    bool fl=true;
    cout<<"kol-vo vershin:  ";
    cin>>n;
    // здесь делаете заполнение графа смежности нулями и единицами (0 - нет пути, 1 - есть пусть)
    while(true)
    {
        for(i=0; i<n; i++)
            if(b[i]==0)
            {
                b[i]=1;
                q[0]=i;
                break;
            }
        if(i==n)
            break;
        i_st=0; i_end=1;
        while(i_st<i_end)
        {
            for(i=0; i<n; i++)
                if((a[q[i_st]][i] || a[i][q[i_st]]) && q[i_st]!=i)
                {
                    if(b[i]==0)
                    {
                        q[i_end++]=i;
                        if(b[q[i_st]]==1)
                            b[i]=2;
                        else
                            b[i]=1;
                    }
                    else
                    {
                        if(b[q[i_st]]==b[i])
                            fl=false;                   
                    }
                }
            i_st++;
        }
    }
    if(fl) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

#pragma once
#include <time.h>
#include <Windows.h>
#include <math.h>
#include <stdio.h>
#include "GlobalVars.h"
 
namespace print_graf {
 
    using namespace System;
    using namespace System::ComponentModel;
    using namespace System::Collections;
    using namespace System::Windows::Forms;
    using namespace System::Data;
    using namespace System::Drawing;
 
    /// <summary>
    /// Сводка для Form1
    /// </summary>
    public ref class Form1 : public System::Windows::Forms::Form
    {
    public:
        Form1(void)
        {
            InitializeComponent();
            //
            //TODO: добавьте код конструктора
            //
        }
 
    protected:
        /// <summary>
        /// Освободить все используемые ресурсы.
        /// </summary>
        ~Form1()
        {
            if (components)
            {
                delete components;
            }
        }
    private: System::Windows::Forms::Panel^  panel1;
    private: System::Windows::Forms::Button^  button1;
    private: System::Windows::Forms::GroupBox^  groupBox1;
    private: System::Windows::Forms::Button^  button2;
    private: System::Windows::Forms::Label^  label2;
    private: System::Windows::Forms::Label^  label1;
    private: System::Windows::Forms::NumericUpDown^  numericUpDown2;
    private: System::Windows::Forms::NumericUpDown^  numericUpDown1;
    private: System::Windows::Forms::Button^  button3;
    private: System::Windows::Forms::Label^  label3;
    private: System::Windows::Forms::NumericUpDown^  numericUpDown3;
    private: System::Windows::Forms::GroupBox^  groupBox2;
    private: System::Windows::Forms::Button^  button4;
    private: System::Windows::Forms::NumericUpDown^  numericUpDown5;
    private: System::Windows::Forms::Label^  label5;
    private: System::Windows::Forms::NumericUpDown^  numericUpDown4;
    private: System::Windows::Forms::Label^  label4;
 
    private: System::Windows::Forms::Button^  button5;
    private: System::Windows::Forms::Label^  label6;
 
    protected: 
 
    private:
        /// <summary>
        /// Требуется переменная конструктора.
        /// </summary>
        System::ComponentModel::Container ^components;
 
#pragma region Windows Form Designer generated code
        /// <summary>
        /// Обязательный метод для поддержки конструктора - не изменяйте
        /// содержимое данного метода при помощи редактора кода.
        /// </summary>
        void InitializeComponent(void)
        {
            this->panel1 = (gcnew System::Windows::Forms::Panel());
            this->button1 = (gcnew System::Windows::Forms::Button());
            this->groupBox1 = (gcnew System::Windows::Forms::GroupBox());
            this->label3 = (gcnew System::Windows::Forms::Label());
            this->numericUpDown3 = (gcnew System::Windows::Forms::NumericUpDown());
            this->button2 = (gcnew System::Windows::Forms::Button());
            this->label2 = (gcnew System::Windows::Forms::Label());
            this->label1 = (gcnew System::Windows::Forms::Label());
            this->numericUpDown2 = (gcnew System::Windows::Forms::NumericUpDown());
            this->numericUpDown1 = (gcnew System::Windows::Forms::NumericUpDown());
            this->button3 = (gcnew System::Windows::Forms::Button());
            this->groupBox2 = (gcnew System::Windows::Forms::GroupBox());
            this->button4 = (gcnew System::Windows::Forms::Button());
            this->numericUpDown5 = (gcnew System::Windows::Forms::NumericUpDown());
            this->label5 = (gcnew System::Windows::Forms::Label());
            this->numericUpDown4 = (gcnew System::Windows::Forms::NumericUpDown());
            this->label4 = (gcnew System::Windows::Forms::Label());
            this->button5 = (gcnew System::Windows::Forms::Button());
            this->label6 = (gcnew System::Windows::Forms::Label());
            this->groupBox1->SuspendLayout();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown3))->BeginInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown2))->BeginInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown1))->BeginInit();
            this->groupBox2->SuspendLayout();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown5))->BeginInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown4))->BeginInit();
            this->SuspendLayout();
            // 
            // panel1
            // 
            this->panel1->Anchor = static_cast<System::Windows::Forms::AnchorStyles>((((System::Windows::Forms::AnchorStyles::Top | System::Windows::Forms::AnchorStyles::Bottom) 
                | System::Windows::Forms::AnchorStyles::Left) 
                | System::Windows::Forms::AnchorStyles::Right));
            this->panel1->BackColor = System::Drawing::Color::White;
            this->panel1->Location = System::Drawing::Point(13, 13);
            this->panel1->Name = L"panel1";
            this->panel1->Size = System::Drawing::Size(498, 492);
            this->panel1->TabIndex = 0;
            // 
            // button1
            // 
            this->button1->Location = System::Drawing::Point(540, 13);
            this->button1->Name = L"button1";
            this->button1->Size = System::Drawing::Size(198, 30);
            this->button1->TabIndex = 1;
            this->button1->Text = L"Вывод графа";
            this->button1->UseVisualStyleBackColor = true;
            this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);
            // 
            // groupBox1
            // 
            this->groupBox1->Controls->Add(this->label3);
            this->groupBox1->Controls->Add(this->numericUpDown3);
            this->groupBox1->Controls->Add(this->button2);
            this->groupBox1->Controls->Add(this->label2);
            this->groupBox1->Controls->Add(this->label1);
            this->groupBox1->Controls->Add(this->numericUpDown2);
            this->groupBox1->Controls->Add(this->numericUpDown1);
            this->groupBox1->Location = System::Drawing::Point(540, 70);
            this->groupBox1->Name = L"groupBox1";
            this->groupBox1->Size = System::Drawing::Size(200, 145);
            this->groupBox1->TabIndex = 2;
            this->groupBox1->TabStop = false;
            this->groupBox1->Text = L"Добавление ребра";
            // 
            // label3
            // 
            this->label3->AutoSize = true;
            this->label3->Location = System::Drawing::Point(71, 63);
            this->label3->Name = L"label3";
            this->label3->Size = System::Drawing::Size(59, 13);
            this->label3->TabIndex = 6;
            this->label3->Text = L"Вес ребра";
            // 
            // numericUpDown3
            // 
            this->numericUpDown3->Location = System::Drawing::Point(6, 82);
            this->numericUpDown3->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {100000, 0, 0, 0});
            this->numericUpDown3->Name = L"numericUpDown3";
            this->numericUpDown3->Size = System::Drawing::Size(187, 20);
            this->numericUpDown3->TabIndex = 5;
            // 
            // button2
            // 
            this->button2->Location = System::Drawing::Point(6, 108);
            this->button2->Name = L"button2";
            this->button2->Size = System::Drawing::Size(187, 30);
            this->button2->TabIndex = 4;
            this->button2->Text = L"Добавить";
            this->button2->UseVisualStyleBackColor = true;
            this->button2->Click += gcnew System::EventHandler(this, &Form1::button2_Click);
            // 
            // label2
            // 
            this->label2->AutoSize = true;
            this->label2->Location = System::Drawing::Point(130, 19);
            this->label2->Name = L"label2";
            this->label2->Size = System::Drawing::Size(22, 13);
            this->label2->TabIndex = 3;
            this->label2->Text = L"До";
            // 
            // label1
            // 
            this->label1->AutoSize = true;
            this->label1->Location = System::Drawing::Point(7, 20);
            this->label1->Name = L"label1";
            this->label1->Size = System::Drawing::Size(20, 13);
            this->label1->TabIndex = 2;
            this->label1->Text = L"От";
            // 
            // numericUpDown2
            // 
            this->numericUpDown2->Location = System::Drawing::Point(130, 36);
            this->numericUpDown2->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {99, 0, 0, 0});
            this->numericUpDown2->Name = L"numericUpDown2";
            this->numericUpDown2->Size = System::Drawing::Size(64, 20);
            this->numericUpDown2->TabIndex = 1;
            // 
            // numericUpDown1
            // 
            this->numericUpDown1->Location = System::Drawing::Point(6, 36);
            this->numericUpDown1->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {99, 0, 0, 0});
            this->numericUpDown1->Name = L"numericUpDown1";
            this->numericUpDown1->Size = System::Drawing::Size(63, 20);
            this->numericUpDown1->TabIndex = 0;
            // 
            // button3
            // 
            this->button3->Location = System::Drawing::Point(540, 383);
            this->button3->Name = L"button3";
            this->button3->Size = System::Drawing::Size(198, 30);
            this->button3->TabIndex = 3;
            this->button3->Text = L"Сохранить в файл";
            this->button3->UseVisualStyleBackColor = true;
            this->button3->Click += gcnew System::EventHandler(this, &Form1::button3_Click);
            // 
            // groupBox2
            // 
            this->groupBox2->Controls->Add(this->button4);
            this->groupBox2->Controls->Add(this->numericUpDown5);
            this->groupBox2->Controls->Add(this->label5);
            this->groupBox2->Controls->Add(this->numericUpDown4);
            this->groupBox2->Controls->Add(this->label4);
            this->groupBox2->Location = System::Drawing::Point(540, 241);
            this->groupBox2->Name = L"groupBox2";
            this->groupBox2->Size = System::Drawing::Size(200, 104);
            this->groupBox2->TabIndex = 4;
            this->groupBox2->TabStop = false;
            this->groupBox2->Text = L"Удаление ребра";
            // 
            // button4
            // 
            this->button4->Location = System::Drawing::Point(6, 63);
            this->button4->Name = L"button4";
            this->button4->Size = System::Drawing::Size(187, 30);
            this->button4->TabIndex = 4;
            this->button4->Text = L"Удалить";
            this->button4->UseVisualStyleBackColor = true;
            this->button4->Click += gcnew System::EventHandler(this, &Form1::button4_Click);
            // 
            // numericUpDown5
            // 
            this->numericUpDown5->Location = System::Drawing::Point(130, 37);
            this->numericUpDown5->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {99, 0, 0, 0});
            this->numericUpDown5->Name = L"numericUpDown5";
            this->numericUpDown5->Size = System::Drawing::Size(64, 20);
            this->numericUpDown5->TabIndex = 3;
            // 
            // label5
            // 
            this->label5->AutoSize = true;
            this->label5->Location = System::Drawing::Point(130, 20);
            this->label5->Name = L"label5";
            this->label5->Size = System::Drawing::Size(22, 13);
            this->label5->TabIndex = 2;
            this->label5->Text = L"До";
            // 
            // numericUpDown4
            // 
            this->numericUpDown4->Location = System::Drawing::Point(7, 37);
            this->numericUpDown4->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {99, 0, 0, 0});
            this->numericUpDown4->Name = L"numericUpDown4";
            this->numericUpDown4->Size = System::Drawing::Size(62, 20);
            this->numericUpDown4->TabIndex = 1;
            // 
            // label4
            // 
            this->label4->AutoSize = true;
            this->label4->Location = System::Drawing::Point(7, 20);
            this->label4->Name = L"label4";
            this->label4->Size = System::Drawing::Size(20, 13);
            this->label4->TabIndex = 0;
            this->label4->Text = L"От";
            // 
            // button5
            // 
            this->button5->Location = System::Drawing::Point(540, 430);
            this->button5->Name = L"button5";
            this->button5->Size = System::Drawing::Size(198, 31);
            this->button5->TabIndex = 7;
            this->button5->Text = L"Граф двудольный\?";
            this->button5->UseVisualStyleBackColor = true;
            this->button5->Click += gcnew System::EventHandler(this, &Form1::button5_Click);
            // 
            // label6
            // 
            this->label6->AutoSize = true;
            this->label6->Location = System::Drawing::Point(629, 475);
            this->label6->Name = L"label6";
            this->label6->Size = System::Drawing::Size(12, 13);
            this->label6->TabIndex = 8;
            this->label6->Text = L"/";
            // 
            // Form1
            // 
            this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
            this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
            this->ClientSize = System::Drawing::Size(748, 513);
            this->Controls->Add(this->label6);
            this->Controls->Add(this->button5);
            this->Controls->Add(this->groupBox2);
            this->Controls->Add(this->button3);
            this->Controls->Add(this->groupBox1);
            this->Controls->Add(this->button1);
            this->Controls->Add(this->panel1);
            this->Name = L"Form1";
            this->Text = L"Рисование графа";
            this->Load += gcnew System::EventHandler(this, &Form1::Form1_Load);
            this->groupBox1->ResumeLayout(false);
            this->groupBox1->PerformLayout();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown3))->EndInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown2))->EndInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown1))->EndInit();
            this->groupBox2->ResumeLayout(false);
            this->groupBox2->PerformLayout();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown5))->EndInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^  >(this->numericUpDown4))->EndInit();
            this->ResumeLayout(false);
            this->PerformLayout();
 
        }
#pragma endregion
 
    int koll_el;
 
    private: System::Void Form1_Load(System::Object^  sender, System::EventArgs^  e) {
    koll_el=0;
    FILE *f1;
    
        int i=0,j=0,x=0,y=0,ves=0,max_x=-1,max_y=-1;
        for(i=0;i<100;i++)
            for(j=0;j<100;j++)
                graf[i][j]=-1;
        if((f1 = fopen("input.txt","r"))!=NULL)
        {
        try
        {
        
        for(i=0;i<10000;i++)
            {
                if(fscanf(f1,"%d",&x)==EOF)
                    break;
                if(x>max_x)
                    max_x=x;
                if(fscanf(f1,"%d",&y)==EOF)
                    break;
                if(y>max_y)
                    max_y=y;
                if(fscanf(f1,"%d",&ves)==EOF)
                    break;
                graf[x][y]=ves;
            }
 
        if(max_x>max_y)
            koll_el=max_x+1;
        else
            koll_el=max_y+1;
        fclose(f1);
        }
    catch(...)
        {fclose(f1);}
        }
    }
    private: System::Void button1_Click(System::Object^  sender, System::EventArgs^  e) {
             
             /*
             srand(time(NULL));
             n=rand()%N;
             g->DrawEllipse(blackPen,250,200,100,100);
             */
             int max_x=0,max_y=0;
             for(int i=0;i<100;i++)
                 for(int j=0;j<100;j++)
                 {
                     if(graf[i][j]!=-1)
                     {
                         if(i>max_x)
                             max_x=i;
                         if(j>max_y)
                             max_y=j;
                     }
                 }
             if(max_x>max_y)
                 koll_el=max_x+1;
             else
                 koll_el=max_y+1;
 
             Point p1;
             Point p2;
             PointF Location;
             System::Drawing::Font^Font;
             double pi = 3.14159265359;
             int n =koll_el;
             //n=10;
             double k;
             k=(n*8.4)/10;
             double x = 150,y = 200;
             IntPtr hwnd = panel1->Handle;
             Graphics^ g = Graphics::FromHwnd( hwnd );
             Brush ^brush = gcnew SolidBrush(Color::White);
             Pen ^blackPen = gcnew Pen(Color::Black);
             Pen ^redPen = gcnew Pen(Color::Red,2);
             g->FillRectangle(brush,RectangleF(0,0,panel1->Width,panel1->Height));
 
             /*---Отрисовка вершин---*/
             for(double i = 0; i < n; i++)
             {
                 x = 100 * cos (i/(n-k))+200;
                 y = 100 * sin (i/(n-k))+200;
 
                 if(x<250)
                     x-=15;
                 if(y<200)
                     y-=15;
 
                 g->DrawString(Convert::ToString(i), Font = (gcnew System::Drawing::Font(L"Arial", 9, System::Drawing::FontStyle::Regular, System::Drawing::GraphicsUnit::Point,static_cast<System::Byte>(0))), brush=gcnew SolidBrush(Color::Black),Location= System::Drawing::Point(x+2,y+3));
                 
                 g->DrawEllipse(blackPen,x,y,18,18);
             }
 
             for(int i=0;i<100;i++)
                 for(int j=0;j<100;j++)
                 {
                     if(graf[i][j]!=-1&&i!=j)
                     {
                         p1=Point(
                                     x = 100 * cos (i/(n-k))+200,
                                     y = 100 * sin (i/(n-k))+200
                                 );
                         p2=Point(
                                     x = 100 * cos (j/(n-k))+200,
                                     y = 100 * sin (j/(n-k))+200
                                 );
                         g->DrawLine(blackPen,p1,p2);
                        // g->DrawEllipse(redPen,x,y,4,4);
                           
                         
                    /////////////////////////////////////////
                   //---------отрисовка направления-------//
                  /////////////////////////////////////////
 
                         double xs,xf,ys,yf,dx,dy;
                          xs = (100 * cos (i/(n-k))+200);
                          ys = (100 * sin (i/(n-k))+200);
                          xf = (100 * cos (j/(n-k))+200);
                          yf = (100 * sin (j/(n-k))+200);
                         
                         if((xs<xf)&&(ys<yf))
                         {
                            /*---1---*/
                             dx=xf-xs;
                             dy=yf-ys;
                             dx/=3;
                             dy/=3;
 
                             xs=xf-dx;
                             ys=yf-dy;
 
                         }
                         if((xs>xf)&&(ys<yf))
                         {
                            /*---3---*/
                             dx=xs-xf;
                             dy=yf-ys;
                             dx/=3;
                             dy/=3;
 
                             xs=xf+dx;
                             ys=yf-dy;
                         }
                         if((xs<xf)&&(ys>yf))
                         { 
                            /*---2---*/
                             dx=xf-xs;
                             dy=ys-yf;
                             dx/=3;
                             dy/=3;
 
 
                             xs=xf-dx;
                             ys=yf+dy;
                         }
                         if((xs>xf)&&(ys>yf))
                         {
                            /*---4---*/
                             dx=xs-xf;
                             dy=ys-yf;
                             dx/=3;
                             dy/=3;
 
                             xs=xf+dx;
                             ys=yf+dy;
                         }
                         p1=Point(xs,ys);
 
                         p2=Point(
                                     xf,
                                     yf
                                 );
                         g->DrawLine(redPen,p1,p2);
                //-------------------------------------/*/
 
                     }
                     if(graf[i][j]!=-1&&i==j)
                     {
                          x = 100 * cos (i/(n-k))+200;
                          y = 100 * sin (i/(n-k))+200;
                          if(x<250)
                              x-=15;
                          if(y<200)
                              y-=15;
                          g->DrawEllipse(redPen,x,y,18,18);
                     }
 
                 }
                 
             }
    private: System::Void button3_Click(System::Object^  sender, System::EventArgs^  e) {
                FILE *f1;
                f1 = fopen("input.txt","w");
                for(int i=0;i<100;i++)
                    for(int j=0;j<100;j++)
                    {
                        if(graf[i][j]!=-1)
                        {
                            fprintf(f1,"%d\n",i);
                            fprintf(f1,"%d\n",j);
                            fprintf(f1,"%d\n",graf[i][j]);
                        }
                    }
                fclose(f1);
             }
private: System::Void button2_Click(System::Object^  sender, System::EventArgs^  e) {
             int i,j;
             i = Decimal::ToInt32(this->numericUpDown1->Value);
             j = Decimal::ToInt32(this->numericUpDown2->Value);
             graf[i][j] = Decimal::ToInt32(this->numericUpDown3->Value);
         }
private: System::Void button4_Click(System::Object^  sender, System::EventArgs^  e) {
             int i,j;
             i = Decimal::ToInt32(this->numericUpDown4->Value);
             j = Decimal::ToInt32(this->numericUpDown5->Value);
             graf[i][j] = -1;
         }
private: System::Void textBox1_TextChanged(System::Object^  sender, System::EventArgs^  e) {
         }
private: System::Void button5_Click(System::Object^  sender, System::EventArgs^  e) {
    bool fl=true;
    while(true)
    {
        int i;
        for(i=0; i<koll_el; i++)
            if(b[i]==0)
            {
                b[i]=1;
                q[0]=i;
                break;
            }
        if(i==koll_el)
            break;
        i_st=0; i_end=1;
        while(i_st<i_end)
        {
            for(i=0; i<koll_el; i++)
                if(graf[q[i_st]][i] && q[i_st]!=i)
                {
                    if(b[i]==0)
                    {
                        q[i_end++]=i;
                        if(b[q[i_st]]==1)
                            b[i]=2;
                        else
                            b[i]=1;
                    }
                    else
                    {
                        if(b[q[i_st]]==b[i])
                            fl=false;                   
                    }
                }
            i_st++;
        }
    }
    if(fl)
        this->label6->Text = L"Да";
    else
        this->label6->Text = L"Нет";
         }
};
}