Кубический подграф [C++]

[Chelmgn]

Условие. Задан граф G=<V,E>
Вопрос. Существует ли в E непустое подмножество E' такое, что в графе G'=<V,E'> любая вершина имеет степень, равную 3 или 0?

Есть алгоритм. Нужно проверить, корректен ли он, и если нет, то исправить. Также добавить комментарии.


#include <iostream.h>
#include <fstream.h>

struct Stack
{
int v,u;
int numb;
bool key;
Stack *next;
};

int n,m;
bool KEY=false;
typedef Stack* TStack;

TStack push(TStack , int ,int);
TStack pop(TStack);
void Build(TStack);
void OutPut(TStack);
void decrease(TStack ,int);
void increase(TStack ,int);
int deg(TStack,int);
TStack START;
bool K_check(TStack);
bool K_gen(int );
//---------------------------------------------------------------------------
int main()
{
fstream fin("3.TXT");
fin>>n;
fin>>m;

START=new Stack[n+1];
for(int w=0;w<n;w++)
START[w].next =NULL;

Build(START); // построение списка графов
OutPut(START); // вывод списка
cout<<endl<<endl;

for(int i=1;i<n+1;i++)
cout<<i<<" - "<<deg(START,i)<<endl;

if(K_gen(1)) cout<<"KUB";
else cout<<"neKUB";
delete[] START;

cin.get();
return 0;
}
//---------------------------------------------------------------------------

TStack push(TStack START, int v,int numb)
{
TStack q;
q=new Stack;
q->v=v;
q->numb=numb;
q->key=true;
q->next=START;
return q;
}

TStack pop(TStack START)
{
START=START->next;
return START;
}

//Построение списка инцидентности
void Build(TStack START)
{
fstream fin("3.TXT");
fin>>n;
fin>>m;
while(!fin.eof())
{
int u,v,numb;
fin>>u;
fin>>v;
fin>>numb;
START[u-1].next=push(START[u-1].next,v,numb);
START[v-1].next=push(START[v-1].next,u,numb);
}
fin.close();
}

//Вывод списка инцидентности
void OutPut(TStack START)
{
for(int k=0;k<n;k++)
{
cout<<k+1<<" -> ";
TStack Temp;
Temp=START[k].next;
while(Temp!=NULL)
{if(Temp->key)
{
cout<<Temp->v<<" -> ";
}
Temp=Temp->next;
if(Temp==0) cout<<"NIL";
}
cout<<endl;}
}

int deg(TStack START, int x) // степень вершины
{
int V=0;

TStack Temp;
Temp=START[x-1].next;

while(Temp!=NULL)
{
if(Temp->key==true)
V++;
Temp=Temp->next;
}

return V;
}



bool K_check(TStack START)
{
bool k=true;
int x,y=0;
for(int i=1;i<n+1;i++)
{
x=deg(START,i);
if(x!=3)
if(x==0) y++; //проверка на степень 0
else
{
k=false;
break;
}
}
if(y==n) k=false; // все изолир
return k;
}

void decrease(TStack START, int NUMB) // понижение степени
{
TStack Temp=NULL;
for(int i=0;i<n;i++)
{
Temp=START[i].next;
while(Temp!=NULL)
{
if(Temp->numb==NUMB)
{
Temp->key=false;
break;
}
Temp=Temp->next;
}
}
}

void increase(TStack START, int NUMB)
{
TStack Temp=NULL;
for(int i=0;i<n;i++)
{
Temp=START[i].next;
while(Temp!=NULL)
{
if(Temp->numb==NUMB)
{
Temp->key=true;
break;
}
Temp=Temp->next;
}
}
}


bool K_gen(int i)
{
int j;
j=i;
while(j<m+1)
{
if(K_check(START))
{
KEY=true;
return KEY;
}
else
{
decrease(START,j);
K_gen(j+1);
increase(START,j);
j++;
}

}
}