Поиск всех точек сочленения заданного графа, страница 2

5.3. Состав модуля 3:

Функция new_list:

Назначение: создание нового двусвязного списка.

Прототип: list *new_list()

Функция add:

Назначение: добавление элемента в двусвязный список.

Прототип: void add(list *l, int data)

Параметры: l – список, data – значение добавляемого элемента.

5.3. Структура программы по управлению:

6. Текст программы на языке C++

main.cpp

#include <stdio.h>

#include "list.h"

#include "graph.h"

int main()

{

       char filename[16];

       printf("Filename: "); gets(filename);

       FILE *f = fopen(filename, "r");

       if (!f)

       {

              perror("Error opening file");

              return 1;

       }

       // Ввод графа

       int N; fscanf(f, "%d", &N);

       list** G = new list*[N];

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

       {

              G[i] = new_list();

       }

       int M; fscanf(f, "%d", &M);

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

       {

              int from, to;

              fscanf(f, "%d %d", &from, &to); from--; to--;

              add(G[from], to);

              add(G[to], from);

       }

       // Поиск

       bool* cutpoints = new bool[N];

       if (find_cutpoints(G, N, cutpoints))

       {

              printf("Graph cutpoints:");

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

              {

                     if (cutpoints[i])

                     {

                            printf(" %d", i + 1);

                     }

              }

              printf("\n");

       }

       else

       {

              printf("Graph has no cutpoints\n");

       }

       delete[] cutpoints;

       return 0;

}

graph.h

#include "list.h"

bool find_cutpoints(list** G, int n, bool* dst_array);

graph.cpp

#include "graph.h"

void dfs(list** G, int n, bool* dst_array,

               int v, int p, int* timer, bool* used, int* tin, int* fup)

{

       used[v] = true;

       tin[v] = fup[v] = (*timer)++;

       int children = 0;

       list* cur = G[v];

       while (G[v] != (cur = cur->next))

       {

              int to = cur->data;

              if (to == p)

              {

                     continue;

              }

              if (used[to])

              {

                     if (tin[to] < fup[v])

                     {

                            fup[v] = tin[to];

                     }

              }

              else

              {

                     children++;

                     dfs(G, n, dst_array, to, v, timer, used, tin, fup);

                     if (fup[to] < fup[v])

                     {

                            fup[v] = fup[to];

                     }

                     if (fup[to] >= tin[v])

                     {

                            dst_array[v] = true;

                     }

              }

       }

       if (p == -1)

       {

              dst_array[v] = children > 1;

       }

}

bool find_cutpoints(list** G, int n, bool* dst_array)

{

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

       {

              dst_array[i] = false;

       }

       bool* used = new bool[n];

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

       {

              used[i] = false;

       }

       int* tin = new int[n];

       int* fup = new int[n];

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

       {

              if (!used[i])

              {

                     int timer = 0;

                     dfs(G, n, dst_array, i, -1, &timer, used, tin, fup);

              }

       }

       delete[] used;

       delete[] tin;

       delete[] fup;

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

       {

              if (dst_array[i])

              {

                     return true;

              }

       }

       return false;

}

list.h

#pragma once

struct list

{

    list *next;

    list *prev;

    int data;

};

list *new_list();

void add(list *, int);

list.cpp

#include "list.h"

list *new_list()

{

    list *l = new list;

    l->data = 0;

    l->next = l;

    l->prev = l;

    return l;

}

void add(list *l, int data)

{

    list *tmp = l->next;

    l->next = new list;

    l->next->prev = l;

    l->next->next = tmp;

    l->next->data = data;

    tmp->prev = l->next;

}

7. Набор тестов

Тест 1: Пустой граф

Входные данные: 5

0

Выходные данные: Graph has no cutpoints

Тест 2: Граф из двух вершин

Входные данные: 2

1

1 2

Выходные данные: Graph has no cutpoints

Тест 3

Входные данные: 4

5

1 2

2 3

3 4

4 1

4 2

Выходные данные: Graph has no cutpoints

Тест 4

Входные данные: 5

6

1 2

2 3

3 4

4 5

5 1

2 4

Выходные данные: Graph has no cutpoints

Тест 5

Входные данные: 6

7

1 2

2 3

3 4

4 5

5 1

2 4

3 6

Выходные данные: Graph cutpoints: 3

Тест 6

Входные данные: 7

8

1 2

2 3

3 4

4 5

5 1

2 4

3 6

6 7

Выходные данные: Graph cutpoints: 3 6

Тест 7

Входные данные: 9

9

1 2

2 3

1 3

3 4

5 6

6 7

7 8

8 5

8 9

Выходные данные: Graph cutpoints: 3 8

Тест 8

Входные данные: 9

10

1 2

2 3

1 3

3 4

5 6

6 7

7 8

8 5

8 9

4 9

Выходные данные: Graph cutpoints: 3 4 8 9