Алгоритм выбора попарно разных значений с n строк

int[] Solve(int[][] aaa)
{
    int[] res = new int[aaa.Length];
    HashSet<int> set = new HashSet<int>();
    for(int i = 0;;)
    {
        int j = res[i];
        if(j >= aaa[i].Length)
        {
            // переходим к следующему брату родителя
            if(--i < 0) return null; // решения нет
            res[i]++;
            continue;
        }
 
        int a = aaa[i][j];
        if(set.Contains(a))
        {
            // переходим к следующему брату текущего узла
            res[i]++; 
            continue;       
        }
        
        set.Add(a);
        // переходим к первому сыну текущего узла
        if(++i >= res.Length)
        {
            // решение найдено
            for(int k = 0; k < res.Length; k++)
                res[k] = aaa[k][res[k]]; // заменяем индексы на числа
            return res; 
        }
        res[i] = 0; 
    }
}

public class Problem
{
    int[][] rows; // массивы индексов чисел, которые может содержать строка 
    List<int> numbers; // значения чисел (по индексу)
    int?[] matchings; // индекс строки, для которой выбрано число (по инедксу)
    
    
    public Problem(int[][] aaa)
    {
        // 1. готовим массив строк и массив чисел
        rows = new int[aaa.Length][];
        numbers = new List<int>();
        Dictionary<int,int> numberIndexes = new Dictionary<int,int>();
        for(int i = 0; i < aaa.Length; i++)
        {
            int[] aa = aaa[i];
            rows[i] = new int[aa.Length]; 
            for(int j = 0; j < aa.Length; j++)
            {
                int a = aa[j];
                int index;
                if(!numberIndexes.TryGetValue(a, out index))
                {
                    index = numbers.Count;
                    numbers.Add(a);
                    numberIndexes.Add(a, index);
                }
                rows[i][j] = index;
            }
        }
    }
    
    public int[] Solve()
    {
        if(numbers.Count < rows.Length)
            return null;
    
        // 2. Сортируем строки в порядке возрастания количества возможных чисел
        int[] rowIndexes = new int[rows.Length];
        for(int i = 0; i < rowIndexes.Length; i++)
            rowIndexes[i] = i;
        Array.Sort(rows, rowIndexes, new ByLengthComparer());   
        
        // 3. Ищем соответсвия для строк методом "первое свободное число"
        matchings = new int?[numbers.Count];
        bool[] hasMatching = new bool[rows.Length];
        for(int i = 0; i < rows.Length; i++)
            for(int j = 0; j < rows[i].Length; j++)
                if(!matchings[rows[i][j]].HasValue)
                {
                    matchings[rows[i][j]] = i;
                    hasMatching[i] = true;
                    break;
                }
    
        // 4. Для оставшихся строк ищем соответсвия поиском в глубину
        visitedRows = new bool[rows.Length];
        for(int i = 0; i < rows.Length; i++)
        {
            if(hasMatching[i])
                continue;
            for(int k = 0; k < visitedRows.Length; k++)
                visitedRows[k] = false;
            if(!Dfs(i))
                return null;
        }
        
        // 5. восстанавливаем исходные номера строк и числа для ответа
        int[] result = new int[rows.Length];
        for(int i = 0; i < matchings.Length; i++)
            if(matchings[i].HasValue)
                result[rowIndexes[matchings[i].Value]] = numbers[i];
        return result;
    }
    
    bool[] visitedRows; 
    bool Dfs(int i)
    {
        if(visitedRows[i]) return false;
        visitedRows[i] = true;
        for(int j = 0; j < rows[i].Length; j++)
        {
            int to = rows[i][j];
            if(!matchings[to].HasValue || Dfs(matchings[to].Value))
            {
                matchings[to] = i;
                return true;
            }
        }
        return false;
    }
    
    private class ByLengthComparer: IComparer<int[]>
    {
        public int Compare(int[] a, int[] b)
        {
            return a.Length.CompareTo(b.Length);
        }
    }
}