Поиск в ширину (доработка программы) - C (СИ)

Формулировка задачи:

Доброго всем времени суток. У меня есть программа, написанная на C, но её нужно несколько переделать. А именно, она должна входные данные считывать из файла, а результат выписывать в виде yes или no (Программа должны определить, является ли граф двудольным). Собственно и сама программа

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
 
#define N   500
 
typedef int graph_t[N][N];
typedef int labels_t[N];
 
struct queue_t
{
    // информационное поле
    int value;
    struct queue_t *next;
};
 
int scan_graph(graph_t graph)
{
    int tops_count, edges_count;
    int i,j,k;
 
    printf("Enter: ");
    scanf("%d",&tops_count);
    scanf("%d",&edges_count);
 
    for (i = 0; i < tops_count; i++)
        for (j = 0; j < tops_count; j++)
            graph[i][j] = 0;
 
    for (k = 0; k < edges_count; k++)
    {
        scanf("%d%d", &i, &j);
        graph[i][j] = 1;
    }
 
    return tops_count;
}
 
void push(struct queue_t **start, struct queue_t **end, int value)
{
    struct queue_t *q = (struct queue_t *)malloc(sizeof(struct queue_t));
 
    q->next = NULL;
    q->value = value;
 
    if (*end != NULL)
    {
        (*end)->next = q;
        *end = q;
    }
    else    
    {
        *start = q;
        *end = *start;
    }
}
 
int pop(struct queue_t **start, struct queue_t **end)
{
    int v = (*start)->value;
 
    struct queue_t *q = (*start)->next;
 
    free(*start);
 
    *start = q;
 
    if (*start == NULL)
        *end = NULL;
    
    return v;
}
 
int tops_count;
graph_t graph;
labels_t labels;
 
void func(graph_t graph, labels_t labels, int tops_count, int start_top)
{
    // поиск в ширину
    int i;
    
    for (i = 0; i < tops_count; i++)
        labels[i] = 0;
 
    struct queue_t *start = NULL, *end = NULL;
 
    push(&start, &end, start_top);
    labels[start_top] = 1;
 
    do
    {
        int top = pop(&start, &end);
        
        for (i = 0; i < tops_count; i++)
            if (!labels[i] && graph[top][i])
            {
                labels[i] = 1;
                push(&start, &end, i);
            }
    } while (start != NULL);
}
 
int main()
{
    int i;
 
    tops_count = scan_graph(graph);
    func(graph,labels,tops_count,0);
    
    for (i = 0; i < tops_count; i++)
        if (labels[i])
            printf("%d ", i);
 
    printf("\n");
 
    getch();
 
    return 0;
}

Решение задачи: «Поиск в ширину (доработка программы)»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
 
typedef int graph_t[100][100];
typedef int labels_t[100];
 
typedef struct _stack_t
{
    int v;
    struct _stack_t *next;
} stack_t;
 
int n;
graph_t g;
 
void push(stack_t **s, int v)
{
    stack_t *t = (stack_t *)malloc(sizeof(stack_t));
    t->v=v;
    t->next=*s;
    *s=t;
}
 
int pop(stack_t **s)
{
    int v = (*s)->v;
    stack_t *next = (*s)->next;
    free(*s);
    *s = next;
    return v;
}
 
int is_component_divided(graph_t g, labels_t *l, int n, int v)
{
    int ans = 1;
    int t = 2;
    int w,i;
    stack_t *s1 = NULL, *s2 = NULL;
 
    (*l)[v] = 1;
    push(&s1, v);
 
    do
    {
        do
        {
            w = pop(&s1);
             
            for (i=0;i < n; i++)
                if (g[w][i])
                {
                    if ((*l)[i] == 0)
                    {
                        (*l)[i] = t;
                        push (&s2,i);
                    }
                    else if ((*l)[i] != t) 
                        ans = 0;
                }
        }
        while (s1 != NULL);
        s1=s2; s2=NULL;
        if (t == 1) t = 2;
        else t = 1;
    } while (s1 != NULL);
 
    return ans;
}
 
int is_divided(graph_t g, int n)
{
    int i;
    int ans = 1;
    labels_t l;
    for (i = 0; i < n; i++)
        l[i]=0;
    for (i = 0; i < n && ans; i++)
        if (l[i] == 0)
            ans = is_component_divided(g,&l,n,i);
            
    return ans;
}
 
void read(graph_t *g, int *n)
{
    int i,j;
    FILE *f = fopen("input.txt","r");
    fscanf(f, "%d",n);
    for(i = 0; i < *n; i++)
        for(j = 0; j < *n; j++)
            fscanf(f,"%d",&(*g)[i][j]);
    fclose (f);
}
 
void write(int ans)
{
    FILE *f = fopen("output.txt","w");
    fprintf(f, ans ? "Yes" : "No");
    fclose(f);
}
 
int main()
{
    read(&g,&n);
    write(is_divided(g,n));
    return 0;
}

Объяснение кода листинга программы

Ввод осуществляется из файла input.txt, а вывод - в файл output.txt.
Функция read считывает из файла число (размер графа) и заполняет матрицу g значениями, соответствующими связности вершин графа.
Функция is_divided проверяет, можно ли разделить граф на два связных компонента, используя алгоритм поиска в ширину. Она принимает граф g, размер графа n и лямбда-функцию l, которая изначально установлена в 0 для всех вершин. Функция проходит по всем вершинам графа и помечает те из них, которые являются началом нового связного компонента. Если все вершины промаркированы, то возвращается 1, иначе - 0.
Функция is_component_divided является вспомогательной и используется внутри is_divided. Она принимает граф g, лямбда-функцию l и размер графа n. Эта функция работает с текущим связным компонентом, помеченным вершиной v. Она помечает все соседние вершины, которые еще не были помечены, и добавляет их в стек. Затем она извлекает вершину из стека и помечает ее как начало нового связного компонента. Если все вершины связного компонента помечены, то возвращается 1, иначе - 0.
Функция push добавляет вершину в стек.
Функция pop извлекает вершину из стека и возвращает ее.
Функция main считывает размер графа из файла, инициализирует граф и вызывает функцию is_divided, которая возвращает 1, если граф можно разделить на два связных компонента, и 0 - в противном случае. Результат записывается в файл output.txt.