Реферат: Графы. Решение практических задач с использованием графов (С++)

#include <stdio.h>

#include <conio.h>

FILE* fi = fopen("m_graph.txt","r");

FILE* fo = fopen("m_par.txt","w");

struct edge{ // ребро графа

int b,e;

};

int n; //количество ребер

edge *graph; // массив ребер

edge *matching; // паросочетание

int num_mat; //количество паросочетаний

bool smezh(edge q1,edge q2){ // 1 - если q1 и q2 смежны, иначе -0

return q1.b==q2.b||q1.b==q2.e||q1.e==q2.b||q1.e==q2.e;

}

void out(edge *m,int num){

fprintf(fo,"%d\n",num); // количество ребер

for(int i=0;i<num;i++)

fprintf(fo,"%d\ %d\n",m[i].b,m[i].e);

}

bool bad(){//возвращает 1, если в паросочетании есть смежное ребро

for(int i=0;i<num_mat-1;i++)

if(smezh(matching[i],matching[num_mat-1]))return 1;

return 0;

}

void solve(){ //находит максимальное паросочетание

num_mat = 0;

for(int i=0;i<n;i++){

matching[num_mat]=graph[i];num_mat++; // добавляем ребро

if(bad())num_mat--; // если уже есть смежные - удаляем