Bipartit1

#include <fstream>

using namespace std;

ifstream f ("bipartit1.in");
ofstream g ("bipartit1.out");

int n,m, w[20][20],a[20],st[20],v[20];

void citire()
{
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        w[x][y]=w[y][x]=1;
    }
}

bool valid (int k)
{
    if(st[k]<=st[k-1])
        return 0;
    return 1;
}

bool partitie(int k)
{
    int s=1;
    for(int i=1;i<=n;i++)
        if(st[s]==i)
            v[i]=1,s++;
        else
            v[i]=2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(v[i]==v[j] && w[i][j]==1)
                return 0;
        }
    return 1;
}

void genpar(int k)
{
    for(int i=1;i<=n;i++)
    {
        st[k]=i;
        if(valid(k))
        {
            if(k<=n/2)
            {
                if(k==n/2)
                {if(partitie(k))
                    {
                    g<<"DA"<<endl;
                       if(v[1]==1)
                       {
                           for(int i=1;i<=k;i++)
                                if(v[i]==1)
                                    g<<i<<" ";
                                g<<endl;
                            for(int i=1;i<=k;i++)
                                if(v[i]==2)
                                    g<<i<<" ";
                       }
                       else
                       {
                            for(int i=1;i<=k;i++)
                                if(v[i]==2)
                                    g<<i<<" ";
                            g<<endl;
                            for(int i=1;i<=k;i++)
                                if(v[i]==1)
                                    g<<i<<" ";
                       }
                    }
                }
                else
                    genpar(k+1);
            }
        }
    }
}

int main()
{
    citire();
    genpar(1);

    return 0;
}