// Нахождение максимального паросочетания в двудольном графе K(M, M). // Написал Поляков С. (2:4625/44.85@fidonet, moongroup@yahoo.com) #include <stdio.h> #define N 9 // Число ребер #define M 5 // Число вершин в двудольном графе int b[M*2][M*2]; // Матрица смежности int a[N][2] = { // Ребра {0, 5}, {0, 7}, {1, 5}, {1, 7}, {2, 6}, {2, 9}, {3, 6}, {3, 8}, {4, 8}}; int vertex[M*2]; // Насыщенность вершин int was[M*2]; int ok; void findpath(int k, int dest) // Поиск пути в графе (Методом поиска в ширину). { int i; if (ok) return; if (k == dest) { ok = 1; return; } for (i = 0; i < M*2; i++) if (i != k) if (b[k][i]) if (was[i] == -1) { was[i] = k; findpath(i, dest); if (!ok) was[i] = -1; } } void reverse(int src, int dest) // Увеличение относительно найденной цепи { int i, j; i = dest; while (i != src) { j = was[i]; b[j][i] = 0; b[i][j] = 1; i = j; } } void main() { int i, j, k; // Инициализация for (i = 0; i < M*2; i++) vertex[i] = 0; for (i = 0; i < M*2; i++) for (j = 0; j < M*2; j++) b[i][j] = 0; // Построение начального паросочетания for (i = 0; i < N; i++) if ((vertex[a[i][0]] == 0) && (vertex[a[i][1]] == 0)) { full[i] = 1; vertex[a[i][0]] = 1; vertex[a[i][1]] = 1; } // Построение матрицы смежности for (i = 0; i < N; i++) if (full[i]) b[a[i][0]][a[i][1]] = 1; else b[a[i][1]][a[i][0]] = 1; // Увеличение паросочетания for (i = M; i < M*2; i++) if (!vertex[i]) // Если исходная вершина ненасыщена, то { for (j = 0; j < M; j++) if (!vertex[j]) // Если вершина j ненасыщена, то { ok = 0; for (k = 0; k < M*2; k++) was[k] = -1; findpath(i, j); // Есть путь из i в j ? if (ok) // ... да, reverse(i, j); // увеличиваем путь. } } // Вывод результата for (i = 0; i < M; i++) for (j = M; j < M*2; j++) if (b[i][j]) printf("%i %i\n", i, j); printf("\n\n"); }