do_laba1

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <fstream>

using namespace std;

/*Алгоритм проверки графа на двудольность, используя обход в ширину
Произведём серию поисков в ширину.
Т.е. будем запускать поиск в ширину из каждой непосещённой вершины.
Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю.
В процессе поиска в ширину, если мы идём в какую-то новую вершину,
то мы помещаем её в долю, отличную от доли текущей вершину.
Если же мы пытаемся пройти по ребру в вершину, которая уже посещена,
то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях.
В противном случае граф двудольным не является.
По окончании работы алгоритма мы либо обнаружим, что граф не двудолен,
либо найдём разбиение вершин графа на две доли.*/


int main() {
ofstream out("out.txt");
ifstream in("in.txt");
int n,j=0,k=0,d=0;
int s; // стартовая вершина (вершины везде нумеруются с нуля)
// чтение графа
in >> n;
//cout << n << endl;
vector < vector<int> > g(n,vector<int>(n)); // граф матрицей смежности

for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
             in >> s;
             g[i][j]=s;
       //    cout << g[i][j] << " ";
        }
    //  cout << endl;
    }
in.close();

s=0;
queue <int> q;
q.push (s);
vector <bool> used(n,false);
vector <int> metki(n);
vector <int> first(n);
vector <int> second(n);
used[s] = true;
for (int i=0;i<n;i++)
{metki[i]= 0;}
metki[s] = 1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    //cout<<"v="<<v<<endl;
    for (int i=0; i<n; ++i) {
        int to = i;
//cout<<"to="<<to<<endl;
        if((used[to])  and (g[v][i] == 1)){
            if((metki[to]!= 0) and (metki[to]==metki[v]) and (v!=i))
            {
          // cout<<"No"<<endl;
             d=1;
             break;
            }
        }
        if((!used[to]) and (g[v][i] == 1)){
            used[to] = true;
            q.push (to);
    //cout<<"metki[to]="<<metki[to]<<endl;
            if((metki[to]!= 0) and (metki[to]==metki[v]) and (v!=i))
            {
          // cout<<"No";d=0;break;
            }
            if((metki[to]==0)and(metki[v]==1))
            {
                metki[to]=2;
            }
            if((metki[to] ==0)and(metki[v]==2))
            {
                metki[to]=1;
            }
        //  cout<<"metki[to]="<<metki[to]<<endl;
        }
    }
}
if (d==1){out<<"N";}
if (d==0) {
out<<"Y"<<endl;
for (int i=0;i<n;i++)
{ //cout<<metki[i]<<"metki=";
    if (metki[i]==1)
       {first[j]=i+1; j++; }
    if (metki[i]==2)
{second[k]=i+1; k++;}
}
if(first[0]==1)
{for (int i=0;i<j;i++)
  {out<<first[i]<<" ";}
  out<<endl; out<<0<<endl;
  for (int i=0;i<k;i++)
  {out<<second[i]<<" ";}
  }
if(first[0]!=1)
{  for (int i=0;i<k;i++)
  {out<<second[i]<<" ";}
  out<<endl; out<<0<<endl;
  for (int i=0;i<j;i++)
  {out<<first[i]<<" ";}
  }
}
out.close();
}