Word Ladder II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder-ii/

题目：
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary. For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
 [
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
 ]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
Solution: Idea is from blog: http://blog.csdn.net/niaokedaoren/article/details/8884938

代码：

 class Solution {  
 public:  
     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
     // If A->C and B->C, then traces[C] contains A and B. This is used for recovering the paths.  
     unordered_map<string, vector<string>> traces;   
     queue<string> q;  
     q.push(start);  
     bool found = false;  
     while (!q.empty()) {  
       int size = q.size();  
       unordered_set<string> level;  
       for (int i = 0; i < size; ++i) {  
         string word = q.front(); q.pop();  
         string nextWord = word;  
         for (size_t j = 0; j < nextWord.size(); ++j) {  
           char before = nextWord[j];  
           for (char c = 'a'; c <= 'z'; c++) {  
             if (c == before) continue;  
             nextWord[j] = c;  
             if (nextWord == end)  
               found = true;  
             if (nextWord == end || dict.find(nextWord) != dict.end()) {  
               traces[nextWord].push_back(word);  
               level.emplace(nextWord);  
             }  
           }  
           nextWord[j] = before;  
         }     
       }  
       if (found) break;  
       for (auto it = level.begin(); it != level.end(); it++) {  
         q.push(*it);  
         dict.erase(*it);  
       }  
     }  
     vector<vector<string> > result;  
     vector<string> onePath;  
     if (!traces.empty()) {  
       buildResult(traces, result, onePath, end, start);        
     }  
     return result;  
   }  
   
   // backtracking to target (start word), then reverse the root->leaf order  
   // DFS  
   void buildResult(unordered_map<string, vector<string> > &traces, vector<vector<string>> &result,   
            vector<string> &onePath, string word, const string &target) {  
     if (word == target) { // word = start word   
       vector<string> copy(onePath);  
       copy.push_back(word);  
       reverse(copy.begin(), copy.end());  
       result.push_back(copy);  
       return;  
     }  
     vector<string> &s = traces[word];  
     onePath.push_back(word);  
     for (int i = 0; i < s.size(); ++i) {  
       buildResult(traces, result, onePath, s[i], target);  
     }  
     onePath.pop_back();  
   }    
 };  
   

Word Ladder I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder/

题目：
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

代码：

 class Solution {  
 public:  
   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     queue<pair<string, int> > q; // (word, transformation steps)  
     q.push({start, 1});  
     while (!q.empty()) {  
       pair<string, int> front = q.front(); q.pop();  
       string word = front.first;  
       for (size_t i = 0; i < word.size(); i++) {  
         char before = word[i];      
         for (char c = 'a'; c <= 'z'; c++) {  
           if (c == before) continue;  
           word[i] = c;  
           if (word == end) {  
             return front.second + 1; // return shortest length              
           }  
           if (dict.find(word) != dict.end()) {  
             q.push({word, front.second + 1});  
             dict.erase(word);  
           }  
         }  
         word[i] = before;  
       }  
     }  
     return 0;  
   }  
 };  

Word Search I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/word-search/

题目：
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
 [
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
 ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

代码：

 class Solution {  
 public:  
   vector<pair<int,int> > offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
   bool exist(vector<vector<char> > &board, string word) {  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool> > visited(M, vector<bool>(N, false)); // visiting status   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (existHelper(board, word, 0, i, j, visited)) {  
           return true;  
         }  
       }      
     }  
     return false;  
   }  
   
   bool existHelper(const vector<vector<char> > &board, const string &word, int deep, int i, int j,   
     vector<vector<bool> > &visited) {  
     int M = board.size(), N = board[0].size();    
     if (deep == word.size()) return true;  
     if (i < 0 || i >= M || j < 0 || j >= N) return false;  
     if (board[i][j] != word[deep] || visited[i][j] == true) return false;  
     visited[i][j] = true;  
     for (auto o : offset) {  
       if (existHelper(board, word, deep + 1, i+o.first, j+o.second, visited)) {  
         return true;  
       }  
     }  
     visited[i][j] = false;  
     return false;  
   }  
 };  

Surrounded Regions

来源：

原帖：https://oj.leetcode.com/problems/surrounded-regions/

题目：
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,
 X X X X
 X O O X
 X X O X
 X O X X
After running your function, the board should be:
 X X X X
 X X X X
 X X X X
 X O X X
Solution: Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).

代码：

 // rumtime error  
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') dfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') dfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') dfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') dfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
     
   void dfs(BOARDTYPE &board, int row, int col) {  
     int M = board.size(), N = board[0].size();  
     board[row][col] = 'V';  
     for (auto o : offset) {  
       int i = row + o.first, j = col + o.second;  
       if (i >= 0 && i < M && j >= 0 && j < N && board[i][j] == 'O') {  
         dfs(board, i, j);  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   
   void bfs(BOARDTYPE &board, int row, int col) {  
     if (board[row][col] != 'O') return;  
     int M = board.size(), N = board[0].size();  
     queue<pair<int, int> > q;  
     board[row][col] = 'V';  
     q.push({row, col}); // q.push({i, j}); pair对也可以使用{i, j} instead of make_pair(i,j)  
     while (!q.empty()) {  
       int i = q.front().first, j = q.front().second;  
       q.pop();  
       for (auto o : offset) {  
         int ii = o.first + i, jj = o.second + j;  
         if (ii >= 0 && ii < M && jj >= 0 && jj < N && board[ii][jj] == 'O') {  
           board[ii][jj] = 'V'; // update !!!   
           q.push({ii, jj});  
         }  
       }  
     }  
   }  
   
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') bfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') bfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') bfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') bfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
 };  
   

Clone Graph

来源：Leetcode

原帖：http://oj.leetcode.com/problems/clone-graph/

题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 Solution: 1. DFS. 2. BFS.

代码：

 /**  
  * Definition for undirected graph.  
  * struct UndirectedGraphNode {  
  *   int label;  
  *   vector<UndirectedGraphNode *> neighbors;  
  *   UndirectedGraphNode(int x) : label(x) {};  
  * };  
  */  
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
   //Version 1: DFS, hash-map  
   GraphNode* cloneGraph(GraphNode *node) {  
     MAP map;  
     return cloneGraphHelper(node, map);  
   }  
     
   GraphNode* cloneGraphHelper(GraphNode *node, MAP &map) {  
     if (!node) return NULL;  
     if (map.count(node)) return map[node];        
     GraphNode* newNode = new GraphNode(node->label);  
     map[node] = newNode;  
     for (int i = 0; i < node->neighbors.size(); ++i) {  
       newNode->neighbors.push_back(cloneGraphHelper(node->neighbors[i], map));  
     }  
     return newNode;  
   }  
 };  
   
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
     
   //Version 2: BFS, HashMap  
   GraphNode *cloneGraph(GraphNode *node) {  
     if (!node) return NULL;  
     queue<GraphNode*> q;  
     q.push(node);  
     MAP map;  
     map[node] = new GraphNode(node->label);  
     while (!q.empty()) {  
       GraphNode *oriNode = q.front();   
       q.pop();  
       GraphNode *newNode = map[oriNode];  
       for (int i = 0; i < oriNode->neighbors.size(); ++i) {  
         GraphNode *oriNeighbor = oriNode->neighbors[i];  
         if (map.find(oriNeighbor) != map.end()) {  
           newNode->neighbors.push_back(map[oriNeighbor]); // already visited!不再加入队列中  
           continue;  
         }  
         GraphNode *newNeighbor = new GraphNode(oriNeighbor->label);  
         newNode->neighbors.push_back(newNeighbor);  
         map[oriNeighbor] = newNeighbor; // set up hash-map  
         q.push(oriNeighbor); // push for next visit  
       }  
     }  
     return map[node];  
   }  
 };  

Sum Root to Leaf Numbers

来源：Leetcode

原帖：https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

题目：
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers.
For example,
   1
  / \
 2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val; *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   int sumNumbers(TreeNode *root) {  
     int sum = 0;  
     sumNumbersHelper(root, 0, sum);  
     return sum;  
   }  
     
   void sumNumbersHelper(TreeNode *node, int num, int &sum) {  
     if (!node) return;  
     num = num * 10 + node->val;  
     if (!node->left && !node->right) {   
       sum += num;  
       return;  
     }  
     sumNumbersHelper(node->left, num, sum);  
     sumNumbersHelper(node->right, num, sum);  
   }  
 };  
   
 class Solution {  
 public:  
   int sumNumbers(TreeNode *root) {  
     if (!root) return 0;      
     int res = 0;  
     queue<pair<TreeNode*, int> > q;  
     q.push(make_pair(root, 0));  
     while (!q.empty()) {  
       TreeNode *node = q.front().first;  
       int sum = q.front().second * 10 + node->val;  
       q.pop();  
       if (!node->left && !node->right) {  
         res += sum;  
         continue;  
       }       
       if (node->left) q.push(make_pair(node->left, sum));          
       if (node->right) q.push(make_pair(node->right, sum));  
     }  
     return res;  
   }  
 };  

Minimum Depth of Binary Tree

来源：Leetcode

原帖：https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/

题目：
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 // 16ms  
 class Solution {  
 public:  
   int minDepth(TreeNode *root) {  
     if (!root) return 0;            
     if (!root->left && !root->right) return 1;        
     if (!root->left) return 1 + minDepth(root->right);    
     if (!root->right) return 1 + minDepth(root->left);        
     // root->left && root->right  
     return 1 + min(minDepth(root->left), minDepth(root->right));  
   }  
 };  
   
 // 21ms  
 class Solution {  
 public:  
   int minDepth(TreeNode* root) {  
     if (!root) return 0;  
     int depth = 0;  
     queue<TreeNode*> q;  
     q.push(root);  
     while (!q.empty()) {  
       depth++;  
       int size = q.size();  
       for (int i = 0; i < size; ++i) {  
         TreeNode* node = q.front();  
         q.pop();  
         if (!node->left && !node->right) {  
           return depth; // min depth;  
         }  
         if (node->left) q.push(node->left);  
         if (node->right) q.push(node->right);  
       }  
     }  
   }  
 };  
   

Binary Tree Zigzag Level Order Traversal

来源：Leetcode

原帖：https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

题目：
'Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
     3
    / \
   9  20
      / \
     15  7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

代码：

 class Solution {  
 public:  
   vector<vector<int>> zigzagLevelOrder(TreeNode *root) {  
     vector<vector<int> > res;  
     if (!root) return res;  
     queue<TreeNode *> q;  
     q.push(root);  
     bool left2right = false;  
     while (!q.empty()) {  
       left2right = !left2right;  
       vector<int> level;  
       int size = q.size();  
       for (int i = 0; i < size; ++i) {  
         TreeNode* node = q.front(); q.pop();  
         level.push_back(node->val);  
         if (node->left) {  
           q.push(node->left);  
         }  
         if (node->right) {  
           q.push(node->right);  
         }  
       }  
       if (!left2right) {  
         reverse(level.begin(), level.end());  
       }  
       res.push_back(level);  
     }    
     return res;  
   }  
 };  

Binary Tree Level Order Traversal II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

题目：
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7]
  [9,20],
  [3],
]

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   vector<vector<int> > levelOrderBottom(TreeNode *root) {  
     vector<vector<int> > res;  
     if (!root) return res;  
     queue<TreeNode*> q;  
     q.push(root);  
     while (!q.empty()) {  
       int size = q.size();  
       vector<int> level;  
       for (int i = 0; i < size; ++i) {  
         TreeNode* node = q.front();   
         q.pop();  
         level.push_back(node->val);  
         if (node->left) {  
           q.push(node->left);  
         }  
         if (node->right) {  
           q.push(node->right);  
         }  
       }  
       res.push_back(level);  
     }  
     // reverse (one more function!)  
     reverse(res.begin(), res.end());  
     return res;  
   }  
 };  

Binary Tree Level Order Traversal I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

题目：
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   //Version 1: BFS  
   vector<vector<int> > levelOrder(TreeNode *root) {  
     vector<vector<int> > res;  
     if (!root) return res;  
     queue<TreeNode*> q;  
     q.push(root);  
     while (!q.empty()) {  
       int size = q.size();  
       vector<int> level;  
       for (int i = 0; i < size; ++i) {  
         TreeNode* node = q.front();   
         q.pop();  
         level.push_back(node->val);  
         if (node->left) {  
           q.push(node->left);  
         }  
         if (node->right) {  
           q.push(node->right);  
         }  
       }  
       res.push_back(level);  
     }  
     return res;  
   }  
 };  
   
 // 8ms  
 class Solution {  
 public:  
   //Version 2: dfs(recursion)  
   vector<vector<int>> levelOrder(TreeNode *root) {  
     vector<vector<int> > result;  
     levelOrderHelper(root, 0, result);  
     return result;  
   }  
   
   void levelOrderHelper(TreeNode *node, int level, vector<vector<int>> &result) {  
     if (!node) return;  
     if (result.size() <= level) { // initialize level  
       result.push_back(vector<int>());   
     }  
     result[level].push_back(node->val);  
     levelOrderHelper(node->left, level + 1, result);  
     levelOrderHelper(node->right, level + 1, result);  
   }  
 };  

Print a Binary Tree in Vertical Order

来源：Facebook电面

原帖：http://www.mitbbs.com/article_t/JobHunting/32946511.html
            http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

题目：

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

思路：这道题dfs + map (因为需要key的顺序保存，所以使用map).或者bfs + map也可。

代码版本使用了bfs + map， 由于dfs不能保证层的顺序。

代码：

 struct TreeNode {  
      int val;  
      TreeNode* left, *right;  
      TreeNode(int v) : val(v), left(NULL), right(NULL) {};  
 };  
   
 vector<vector<int>> verticalPrintBinaryTree(TreeNode* root) {  
      vector<vector<int>> res;  
      if (!root) return res;  
      map<int, vector<int>> table;  
      queue<pair<TreeNode*, int>> q;  
      q.push({root, 0});  
      table[0].push_back(root->val);  
   
       while (!q.empty()) {  
           auto node = q.front().first;  
           int label = q.front().second;  
           q.pop();  
           if (node->left) {  
                table[label-1].push_back(node->left->val);  
                q.push({node->left, label-1});  
           }  
           if (node->right) {  
                table[label+1].push_back(node->right->val);  
                q.push({node->right, label+1});  
           }  
      }  
   
       for (auto it = table.begin(); it != table.end(); ++it) {  
           res.push_back(it->second);  
      }  
      return res;  
 }  
   
 void print(vector<vector<int>>& num) {  
      for (int i = 0; i < num.size(); ++i) {  
           for (int j = 0; j < num[i].size(); ++j) {  
                cout << num[i][j] << " ";  
           }  
           cout << endl;  
      }  
 }  
   
 int main() {  
   TreeNode *root = new TreeNode(1);  
   root->left = new TreeNode(2);  
   root->right = new TreeNode(3);  
   root->left->left = new TreeNode(4);  
   root->left->right = new TreeNode(5);  
   root->right->left = new TreeNode(6);  
   root->right->right = new TreeNode(7);  
   root->right->left->right = new TreeNode(8);  
   root->right->right->right = new TreeNode(9);  
   cout << "Vertical order traversal is \n";  
   vector<vector<int>> res = verticalPrintBinaryTree(root);  
   print(res);  
   return 0;  
 }  
   

200 Number of Islands

来源：Leetcode, Google常考题

原帖：https://leetcode.com/problems/number-of-islands/

题目：
Given a 2d grid map of '1's (land) and '0's (water), count 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.
思路：找到连通域的数目，典型的bfs, dfs题目。

代码：DFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int r, int c) {  
         int M = grid.size(), N = grid[0].size();  
         visited[r][c] = true;  
         for (auto o : offset) {  
             int i = r + o.first, j = c + o.second;  
             if (i < 0 || i >= M || j < 0 || j >= N) continue;  
             if (grid[i][j] == '0' || visited[i][j]) continue;  
             dfs(grid, visited, i, j);  
         }  
     }  
   
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     dfs(grid, visited, i,j);  
                 }  
             }  
         }  
         return count;  
     }  
 };  

代码：BFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     queue<pair<int,int>> q;  
                     visited[i][j] = true;  
                     q.push({i,j});  
                     while (!q.empty()) {  
                         auto neigh = q.front(); q.pop();  
                         for (auto o : offset) {  
                             int r = neigh.first + o.first, c = neigh.second + o.second;  
                             if (r < 0 || r >= M || c < 0 || c >= N) continue;  
                             if (visited[r][c] || grid[r][c] == '0') continue;  
                             visited[r][c] = true;  
                             q.push({r,c});  
                         }  
                     }  
                 }  
             }  
         }  
         return count;  
     }  
 };  

Bipartite Graph

来源：Twitter Second Phone Interview, EPI

原帖：http://www.fgdsb.com/2015/01/03/check-whether-a-graph-is-bipartite-or-not/

题目：

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)

Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).

思路：使用BFS遍历

代码：

 // bipartite graph   
 // G=[(1,2), (2,3), (3,4)] yes   
 // G=[(1,2), (2,3), (3,1)] no   
 // G=[(1,2), (2,3), (3,4), (4,1)] yes    
   
 // adjacency list   
 struct GraphNode {   
   int visited; // -1 visited, 0: 1-color1; 1: 2-colors;   
   vector<GraphNode*> neighbors;   
 };   
   
 // adjacency matrixs   
 // vector<vector<int>> graph;   
 // vector<int> color(num_nodes);   
   
 bool isBipartite(vector<GraphNode*> g) {   
   if (g.empty()) return false;   
   for (int i = 0; i < g.size(); ++i) {   
     if (g[i]->visited == -1) {   
       g[i]->visited = 0;   
       queue<GraphNode*> q;   
       q.push(g[i]);   
       while (!q.empty()) {   
         auto node = q.front(); q.pop();       
         auto neighbors = node->neighbors;   
         for (int k = 0; k < neighbors.size(); ++k) {   
           if (neighbors[k]->visited == -1) {   
             neighbors[k]->visited = node->visited == 0 ? 1 : 0;   
             q.push(neighbors[k]);   
           } else {   
             if (neighbors[k]->visited == node->visited) return false;   
           }   
         }   
       }   
     }   
   }   
   return true;   
 }