DP medium Flashcards
- Integer Break
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
Можно решить рекурсивной функцией, перебирая на каждом шаге от 1 до половины N включительно.
Dictionary<int, int> memo = new Dictionary<int, int>(){{1,1}};
public int IntegerBreak(int n) {
if(n==1) return 1;
if(n==2) return 1;
if(memo.TryGetValue(n, out int maxProduct))
return maxProduct;
int half = n /2;
int result = 0;
for(int i= 1; i<= half; i++)
{
int a = Math.Max(i, IntegerBreak(i));
int b = Math.Max(n - i, IntegerBreak(n - i));
result = Math.Max(result, a*b);
}
memo[n] = result;
return result;
} Есть еще решение за O(N) , математическое, но доказать его правильность не знаю как
public int IntegerBreak(int n)
{
if (n <= 3) return n - 1;
int result = 1;
while (n > 4)
{
result *= 3;
n -= 3;
}
return result*n;
} типа максимизируем количество троек в числах 10=3+3+2+2 3*3*2*2 - максимум = 36
- Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
DP заключается в том что идет пересчет количество монет для каждой суммы от 1 до amount. и каждая новая сумма опирается на меньшую посчитанную сумму
public int CoinChange(int[] coins, int amount) {
if(amount == 0)
return 0;
int[] countOfCoins = new int[amount+1];
Array.Fill(countOfCoins, -1);
for(int currentAmount = 1; currentAmount <= amount; currentAmount++)
{
foreach(int coin in coins)
if(coin == currentAmount)
countOfCoins[currentAmount] = 1;
else
if(coin < currentAmount)
// и предыдущее почитано и текущее, но предыдущее+1 меньше(лучше) чем текущее
if(countOfCoins[currentAmount-coin] != -1 && (countOfCoins[currentAmount] != -1 && countOfCoins[currentAmount] > countOfCoins[currentAmount-coin] + 1)
||
// предыдущее посчитано а для текущего расчета нет
countOfCoins[currentAmount-coin] != -1 && countOfCoins[currentAmount] == -1
)
// если так то заменяем
countOfCoins[currentAmount] = countOfCoins[currentAmount-coin] + 1;
}
return countOfCoins[amount];
}
- Delete Operation for Two Strings
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
“abbcd” vs “ack”
AKA LongestCommonSubsequence
AKA LCS
Интуитивно понятный ниже - Lagest Common Sequence - если последний символ совпадает, то lcs+1, если нет то выбираем максимальный из 2 вариантов lcs(строка1 -1, строка2) или lcs(строка1, строка-1). все остальное обвязка. без мемоизации - долго. сложность по скорости O(m*n)
public int MinDistance(string word1, string word2) {
int[,] memo = new int[word1.Length, word2.Length];
int lcs(string a, string b, int len1, int len2)
{
if(len1 < 0 || len2 <0)
return 0;
if(memo[len1,len2] > 0)
return memo[len1,len2];
if(a[len1] == b[len2])
memo[len1,len2] = 1 + lcs(a,b, len1-1, len2 -1);
else
memo[len1,len2] = Math.Max(lcs(a,b,len1-1, len2), lcs(a,b,len1, len2-1));
return memo[len1,len2];
}
return word1.Length + word2.Length - 2 * lcs(word1, word2,word1.Length -1, word2.Length -1);
}
Есть второй вариант, не такой очевидный . Вот он прямо - DP. там где рассчитывается на матрице
public int MinDistance(string word1, string word2) {
var dp = new int[word1.Length+1, word2.Length+1];
for(int i = 0; i <= word1.Length; i++)
{
for(int j = 0; j <= word2.Length; j++)
{
if(i == 0 || j == 0) continue;
if(word1[i-1] == word2[j-1])
dp[i,j] = dp[i-1,j-1] +1;
else
dp[i,j] = Math.Max(dp[i-1,j], dp[i,j-1]);
}
}
return word1.Length + word2.Length - dp[word1.Length, word2.Length] * 2;
} так и не понял, почему это работает ((
- Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
A string is called a palindrome string if the reverse of that string is the same as the original string.
Самый очевидный - пытаемся вырастить полиндром из каждой пары (i,i+1) увеличивая левый и правый указатель на 1. если буквы совпали - полиндром вырос, иначе нет. найдем все и выберем максимальный. (а вообще вариантов описано 5 и есть даже именные алгоритмы. )
public string LongestPalindrome(string s) {
if(s.Length == 1)
return s;
List<string> allPoly = new List<string>();
for(int i = 0; i < s.Length-1; i++)
{
allPoly.Add(grow(s, i,i));
allPoly.Add(grow(s, i,i+1));
}
string grow(string s, int i, int j)
{
if(s[i]!= s[j])
return string.Empty;
int left = i;
int right = j;
while(i>=0 && j < s.Length && s[i] == s[j])
{
left = i;
right = j;
i--;
j++;
}
return s.Substring(left,right - left +1);
}
var size = allPoly.Max( item => item.Length);
return allPoly.First( item=> item.Length == size);
}
- Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
DP - создаем 2 массива для хранения максимальной длинны, достигнутой к этому индексу, и количества путей максимальной длинны. закончившихся в этом индексе. т.е. для массива [1,2] len=[1,2] count=[1,1] - индекс это то место которое мы просчитываем.
А дальше идем в два цикла i впереди а j бегает от 0. Кажется что идти с конца более интуитивно, но написать такой код не получилось (( так что просто поверь ((
public int FindNumberOfLIS(int[] nums) {
int[] count = new int[nums.Count()];
int[] len = new int[nums.Count()];
int maxCount = 0; int maxLen = 0;
for(int i = 0; i<nums.Count() ; i++)
{
count[i] = 1; len[i] = 1;
for(int j = 0; j < i; j++)
{
if(nums[i]> nums[j])
{
if(len[i] < len[j] + 1)
{
len[i] = len[j] + 1;
count[i] = count[j];
}
else
if(len[i] == len[j] + 1)
count[i] += count[j];
}
}
// ниже просто код по запоминанию глобального максимума. в принципе можно было забить и вытащить это выражение из циклов через 3 LINQ
if(maxLen < len[i])
{
maxLen = len[i];
maxCount = count[i];
}
else
if(maxLen == len[i])
{
maxCount += count[i];
}
}
return maxCount;
Video: https://www.youtube.com/watch?v=Tuc-rjJbsXU
- Edit Distance
Hard
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character Delete a character Replace a character
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
DP - тут тоже история с 2-х мерной матрицей. так и не понял почему это работает ((
public int MinDistance(string word1, string word2) {
int m = word1.Length;
int n = word2.Length;
if(m*n == 0)
return m+n;
int[,] dp = new int[m+1, n+1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0) {
dp[i, j] = j;
}
else if(j == 0) {
dp[i, j] = i;
}
else if(word1[i -1] == word2[j - 1]) {
dp[i, j] = dp[i -1, j -1];
}
else{
dp[i, j] = Math.Min(dp[i -1, j - 1], Math.Min(dp[i, j -1], dp[i-1, j])) + 1;
}
}
}
return dp[m,n];
}
- Happy Number
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Решается циклом. Вообще есть несколько вариантов решения проблемы “зацикливания”. Здесь через хешмап, но можно и еще через поиск цикла в списке (быстрый и медленный указатель) - но этот интуитивно понятнее. Сложность logN
public bool IsHappy(int n) {
HashSet<int> hash = new HashSet<int>();
int getNext(int n)
{
int summ = 0;
while(n>0)
{
int d = n%10;
n = n / 10;
summ += d*d;
}
return summ;
}
while(n != 1 && !hash.Contains(n))
{
hash.Add(n);
n = getNext(n);
}
return n==1;
}
- Shuffle an Array
Medium
Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it. int[] shuffle() Returns a random shuffling of the array.
Example 1:
Input
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
Странная задача, основной вопрос как пересортировать массив. Удобнее всего - свап - поменять местами. В цикле , каждый элемент свапаем с рандомным. Остальное техника.
- Bitwise AND of Numbers Range
Medium
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example 3:
Input: left = 1, right = 2147483647
Output: 0
В лоб не решается. См. пример, будет таймаут. Так что там есть несколько вариантов как крутить биты, в любом случает
public int RangeBitwiseAnd(int m, int n)
{
if (m == n) return m;
var xor = m ^ n;
int b = 1 «_space;30;
while ((xor & b) == 0)
{
b»_space;= 1;
}
return m & ~((b«1) - 1);
}
хз как это работает
- Generate Parentheses
Medium
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Не хватило времени. Вот такой принял (Backtracking, DP)
public IList<string> GenerateParenthesis(int n) {
var res = new List<string>();
var s = new Stack<(string, int, int)>();
s.Push(("", n, 0 ));</string></string>
while(s.Count != 0)
{
(string currS, int openedNeeded, int closedNeeded) = s.Pop();
if (openedNeeded == 0 && closedNeeded == 0)
res.Add(currS);
if(closedNeeded != 0)
s.Push((currS + ')',openedNeeded, closedNeeded-1));
if (openedNeeded != 0)
s.Push((currS + '(', openedNeeded-1, closedNeeded+1));
}
return res;
}
- Word Search
Medium
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true
Не хватило времени (( Backtracking
bool[,] visited = new bool[6, 6];
public bool Exist(char[][] board, string word)
{
for(int i = 0; i < board.Length; i++)
{
for(int j = 0; j < board[i].Length; j++)
{
if (board[i][j] == word[0])
{
bool exists =
ContainsWord(board, i, j, word, "");
if (exists)
return exists;
}
}
}
return false;
}
public bool ContainsWord(char[][] board, int row,int col,
string word,string res)
{
if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length ||
visited[row, col] || res.Length >= word.Length)
return false;
visited[row, col] = true;
res += board[row][col];
if (res == word)
return true;
bool exits = ContainsWord(board, row + 1, col, word, res)
|| ContainsWord(board, row - 1, col, word, res)
|| ContainsWord(board, row, col-1, word, res)
|| ContainsWord(board, row, col +1, word, res);
visited[row, col] = false;
return exits;
}
- Letter Combinations of a Phone Number
Medium
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Не хватило времени. Backtracking
public IList<string> LetterCombinations(string digits) {
IList<string> result = new List<string>();
Dictionary<char, List<char>> dial = new Dictionary<char, List<char>>();</char></char></string></string></string>
dial.Add('2', new List<char>() {'a', 'b', 'c'});
dial.Add('3', new List<char>() {'d', 'e', 'f'});
dial.Add('4', new List<char>() {'g', 'h', 'i'});
dial.Add('5', new List<char>() {'j', 'k', 'l'});
dial.Add('6', new List<char>() {'m', 'n', 'o'});
dial.Add('7', new List<char>() {'p', 'q', 'r', 's'});
dial.Add('8', new List<char>() {'t', 'u', 'v'});
dial.Add('9', new List<char>() {'w', 'x', 'y', 'z'});
foreach (char c in digits) {
List<char> charsNew = dial[c];
IList<string> temp = new List<string>();
if (result.Count == 0) {
foreach (char cNew in charsNew) {
result.Add(cNew + "");
}
}
else {
foreach (string s in result) {
foreach (char cNew in charsNew) {
temp.Add(s + cNew);
}
}
result = temp;
}
}
return result;
}
- Subsets II
Medium
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Не хватило времени.
public IList<IList<int>> SubsetsWithDup(int[] nums) {
List<IList<int>> l = new List<IList<int>>();
Array.Sort(nums);
Subsets(nums,new List<int>(),0, l);
return l;
}</int></int></int></int>
public IList<IList<int>> Subsets(int[] nums, List<int> current, int index, List<IList<int>> subsets)
{
var currentCopy = new List<int>();
currentCopy.AddRange(current);
subsets.Add(currentCopy);
for (int i = index; i < nums.Length; i++)
{
current.Add(nums[i]);
Subsets(nums, current, i+1, subsets);
current.Remove(nums[i]);
while (i < nums.Length - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
return subsets;
}
- Permutations II
Medium
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Не хватило времени
public IList<IList<int>> PermuteUnique(int[] nums)
{
IList<IList<int>> ans = new List<IList<int>>();
Array.Sort(nums);
Backtrack(nums, new bool[nums.Length], new List<int>(), ans);
return ans;
}</int></int></int></int>
private void Backtrack(int[] nums, bool[] taken, IList<int> li, IList<IList<int>> ans)
{
if(li.Count==nums.Length)
{
ans.Add(new List<int>(li));
return;
}
for(int i=0;i<nums.Length;i++)
{
if(!taken[i] && (i==0 || taken[i-1] || nums[i] != nums[i-1]))
{
taken[i]=true;
li.Add(nums[i]);
Backtrack(nums,taken,li,ans);
taken[i]=false;
li.RemoveAt(li.Count-1);
}
}
}
- Combination Sum
Medium
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Не хватило времени
public class Solution {
List<IList<int>> res = new();
int[] candidates;
int target = 0;</int>
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
Array.Sort(candidates);
Array.Reverse(candidates);
this.candidates = candidates;
this.target = target;
helper(new List<int>(), 0);
return res;
}
public void helper(List<int> lst, int index){
int sum = lst.Sum();
if(sum > target)
return;
else if(sum == target)
res.Add(new List<int>(lst));
else{
for(int i = index; i< candidates.Length; i++){
lst.Add(candidates[i]);
helper(lst, i);
lst.RemoveAt(lst.Count - 1);
}
}
} }
- Combination Sum II
Medium
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Backtracking не хватило времени (( - на страничке есть описание . несколько вариантов решения
public IList<IList<int>> CombinationSum2(int[] candidates, int target)
{
Array.Sort(candidates);
List<IList<int>> results = new();
Stack<int> currentCombination = new();
Backtracking(0, 0);
return results;</int></int></int>
void Backtracking(int index, int currentSum)
{
if (currentSum == target)
{
results.Add(currentCombination.ToArray());
return;
}
if (index == candidates.Length) return;
if (currentSum > target) return;
currentCombination.Push(candidates[index]);
Backtracking(index + 1, currentSum + candidates[index]);
currentCombination.Pop();
while (index + 1 < candidates.Length && candidates[index] == candidates[index + 1])
{
index++;
}
Backtracking(index + 1, currentSum);
}
}
- Populating Next Right Pointers in Each Node II
Medium
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.
Не хватило времени.
public Node Connect(Node root)
{
if(root == null) return root;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while(q.Count != 0)
{
List<Node> level = new List<Node>();
int size = q.Count;
for(int i = 0; i < size; i++)
{
Node curr = q.Dequeue();
level.Add(curr);
if(curr.right != null) q.Enqueue(curr.right);
if(curr.left != null) q.Enqueue(curr.left);
}
for(int i = level.Count - 1; i >= 1; i--)
{
level[i].next = level[i - 1];
}
}
return root;
}
- Number of Islands
Medium
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Делал раньше. Идея - находим первую сушу, счетчик++, и заливаем эту землю рекурсивно водой
public int NumIslands(char[][] grid) {
int counter = 0;
for(int i=0; i< grid.Length; i++)
for(int j=0; j <grid[i].Length; j++)
{
if(grid[i][j] == ‘1’) // laaaand!!!!
{
counter++;
dfs(grid,i,j); // sink that island
}
}
return counter;
}
void dfs(char[][] grid, int i, int j)
{
if(i<0 || i>= grid.Length || j< 0 || j >= grid[i].Length || grid[i][j] == '0')
return;
grid[i][j] = '0';
dfs(grid, i - 1, j );
dfs(grid, i + 1, j );
dfs(grid, i, j - 1 );
dfs(grid, i, j + 1 );
}
- Max Points on a Line
Hard
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
И одна красная задача. Не хватило времени. Теги: math,geometry,hashtable
public int MaxPoints(int[][] points) {
var max = 0;
for(int i=0; i<points.Length-1; i++)
{
var dictionary = new Dictionary<double, int>();
for(int j=i+1; j<points.Length; j++)
{
double slope;
//If divide by zero
if(points[j][0] == points[i][0]) slope = Double.MaxValue;
else slope = (double)(points[j][1] - points[i][1])/(points[j][0] - points[i][0]);
if(dictionary.ContainsKey(slope))
{
dictionary[slope] = dictionary[slope] +1;
}
else dictionary.Add(slope, 1);
max = Math.Max(max, dictionary[slope]);
}
}
return (max+1);
}
- Find Eventual Safe States
There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
medium - ищем все узлы которые ведут к безопасным
public class Solution
{
public IList<int> EventualSafeNodes(int[][] graph)
{
Dictionary<int, bool> isLeadingToTerminal = new();
return Enumerable.Range(0, graph.Length).Where(IsLeadingToTerminal).ToArray();</int>
bool IsLeadingToTerminal(int node)
{
if (isLeadingToTerminal.ContainsKey(node)) return isLeadingToTerminal[node];
isLeadingToTerminal[node] = false;
return isLeadingToTerminal[node] = graph[node].All(IsLeadingToTerminal);
}
} }
- Shortest Path Visiting All Nodes
Hard
You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
Hard . Тут еще и манипулирование битами (!)
public class Solution
{
public int ShortestPathLength(int[][] graph)
{
int res = 0, fullMask = (1 «_space;graph.Length) - 1;
HashSet<(int, int)> used = new();
Queue<(int mask, int v)> queue = new(Enumerable.Range(0, graph.Length).Select(i => (1 << i, i)));
while (queue.Any())
{
for (int count = queue.Count; count > 0; --count)
{
var pos = queue.Dequeue();
if (used.Contains(pos)) continue;
if (pos.mask == fullMask) return res;
used.Add(pos);
foreach (int u in graph[pos.v]) queue.Enqueue((pos.mask | (1 << u), u));
}
\++res;
}
throw new ArgumentException("Graph isn't connected");
} }
