Поиск максимальных пар из заданного массива

Question

У меня есть массив Pairs[n][n].

Если Pairs[i][j]==true это означает, что блок i и j могут образовать пару.

Я должен найти максимальную пару, которую я могу сформировать из данного массива со следующим условием:
Блок может быть парным ноль или один раз.
Вы не можете подключить более двух блоков
Я не могу придумать какой-либо подход, не могли бы вы предложить мне алгоритм, как подойти к этой проблеме.

Answer 1

Проверьте это.

 int n = 10; 
     bool[,] array = new bool[n, n]; 

     List<Tuple<int, int>> pairs = new List<Tuple<int, int>>(); 

     for (int row = 0; row < array.GetLength(0); row++) 
     { 
      for (int col = 0; col < array.GetLength(1); col++) 
      { 
       if (array[row, col] == true) 
       { 
        pairs.Add(new Tuple<int, int>(row, col)); 
       } 
      } 
     } 

     // Prints the combinations 
     foreach (var pair in pairs) 
     { 
      Console.WriteLine("{0} : {1}", pair.Item1, pair.Item2); 
     } 

Answer 2

Ваш массив представляет собой график, а Pairs[i][j]==true обозначает ребро между Ith и JTH вершинами.

Так что эта проблема maximum matching для общего графика, и возможен подход Edmonds's matching algorithm