Поиск двух городов в системе двусторонних дорог и соединяющего пути длиной не более 100 км, проходящего через каждую дорогу ровно 1 раз, страница 2

                           cout << "Введено несуществующее ребро!";

                           fclose(f);

                           return 0;

                     }

               }

               fclose(f);

               return n;

            } else

            {

               cout << "Невозможно открыть файл 'input.txt'";

               return 0;

            }

}

int ver_deg(int v) //Вычисление степени вершины

{

            int i, s=0;

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

            if (adj[v][i]>0)

            s++;

            return s;

}

void nxt(int s) //вспомогательная функция для coherent()

{

            int i;

            if (adj[s][s]!=2)

            {

               adj[s][s] = 2;

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

                     if ((adj[s][i]>0) && (adj[i][i]!=2))

                     nxt(i);

            }

}

int coherent() //Проверка графа на связность

{

            int i, yes=1;

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

            if (ver_deg(i) == 0)

            adj[i][i] = 2;

            nxt(0);

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

            {

               if (adj[i][i] != 2)

               yes = 0;

               adj[i][i] = 0;

            }

            return yes;

}

int adj_ver(int v) //Возвращает любую вершину, смежную с данной

{

            int i;

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

            if (adj[v][i]>0)

            return i;

            return -1;

}

int vertex_cond() //Проверка условий, связанных с вершинами

{

            int i, j, s=0, c=0, v=-1;

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

            {

               s = ver_deg(i);

               if ((s>0) && (s%2==1))

               {

                     c++;

                     if (v<0) v = i;

               }

               s = 0;

            }

            if (c==2) return v;

            else return -1;

}

int edges_length() //Вычисление суммы весов ребер

{

            int i, j, s=0;

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

            for (j=i; j<n; j++)

            s += adj[i][j];

            return s;

}

v_l *merge(v_l *r, v_l *z)

{

            v_l *t;

            while (z)

            {

               if (z->v == r->v)

               {

                     t = z->nxt;

                     z->nxt = r->nxt;

                     while (r->nxt) r = r->nxt;

                     r->nxt = t;

                     return z;

               }

               z = z->nxt;

            }

            return z;

}

int all(v_l *z)

{

            while (z)

            {

               if (ver_deg(z->v)>0)

               return 0;

               z = z->nxt;

            }

            return 1;

}

int make_chain(int v) //Построение эйлеровой цепи

{

            int w, i, j;

            v_l *r, *t, *z;

            FILE *f;

            z=new v_l;

            z->v = v;

            z->nxt = NULL;

            do

            {

                     delete r;

                     r=new v_l;

                     r->v = v;

                     r->nxt = NULL;

                     t=r;

                     do

                     {

                           w=adj_ver(v);

                           t = add(t, w);

                           adj[v][w] = adj[w][v] = 0;

                           v=w;

                     } while ((ver_deg(v)>0));

                     merge(r, z);

            } while (all(z));

            f = fopen("output.txt", "wt");

            if (f)

            {

               while (z)

               {

                     fprintf(f, "[%d]-",z->v);

                     z = z->nxt;

               }

               fclose(f);

            } else

            cout << "Невозможно открыть файл 'output.txt'";

}

void main()

{

            clrscr();

            int ed_l, fst_v;

            n = input();

            fst_v = vertex_cond();

            ed_l = edges_length();

            if ((n>1) && (fst_v>-1) && (ed_l>0) && (ed_l<=100) && coherent())

               make_chain(fst_v);

   else

               cout << "Невозможно построить эйлерову цепь в данном графе";

}

5.  Тесты

1)  Ввод:

12

0-2 1

2-1 1

2-3 1

2-4 1

3-5 1

4-5 1

5-6 1

5-7 1

5-8 1

5-9 1

6-7 1

7-8 1

8-9 1

7-10 1

8-11 1

10-11 1

Вывод:

0-2-3-5-6-7-8-9-5-10-11-5-4-2-1

2)  Ввод:

12

0-2 10

2-1 10

2-3 10

2-4 10

3-5 10

4-5 10

5-6 10

5-7 10

5-8 10

5-9 10

6-7 10

7-8 10

8-9 10

7-10 10

8-11 10

10-11 10

Вывод:

Impossible to build eiler chain in this graph

3)  Ввод:

6

0-1 10

2-1 10

2-3 10

3-4 10

4-1 10

1-3 10

Вывод:

0-1-2-4-3-1-4

4)  Ввод:

6

0-2 1

2-1 1

2-3 1

3-5 1

4-2 1

5-4 1

Вывод:

0-2-3-5-4-2-1

5)  Ввод:

2

Вывод:

Impossible to build eiler chain in this graph

6)  Ввод:

6

0-1 10

2-4 10

2-3 10

3-5 10

4-5 10

Вывод:

Impossible to build eiler chain in this graph

6.  Результат

Программа успешно прошла тесты.