Tag Archives: DFS

LeetCode Path Sum

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.


本题要一个数是否等于从树根到某个叶子的和。简单题,直接dfs把所有从根到叶子的路径和算出来,存到set里面,然后用sum去set里查。当然如果还想更高效,可以用hash,比如unordered_map。 完整代码如下:

class Solution {
public:
    void dfs(set<int>& vals, int cur, TreeNode* root)
    {
        if (root->left == NULL && root->right == NULL) {
            vals.insert(cur + root->val);
            return;
        }
        if (root->left != NULL) {
            dfs(vals, cur + root->val, root->left);
        }
        if (root->right != NULL) {
            dfs(vals, cur + root->val, root->right);
        }
    }
    bool hasPathSum(TreeNode* root, int sum)
    {
        if (root == NULL)
            return false;
        set<int> vals;
        dfs(vals, 0, root);
        if (vals.count(sum) > 0)
            return true;
        else
            return false;
    }
};

本代码提交AC,用时13MS。
二刷。直接递归判断某一条路径的和是否等于sum就好了,代码如下:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum)
    {
        if (root == NULL)
            return false;
        if (root->left == NULL && root->right == NULL && root->val == sum)
            return true;
        if (root->left == NULL && root->right == NULL && root->val != sum)
            return false;
        if (root->left != NULL)
            if (hasPathSum(root->left, sum – root->val))
                return true;
        if (root->right != NULL)
            if (hasPathSum(root->right, sum – root->val))
                return true;
        return false;
    }
};

本代码提交AC,用时9MS。

LeetCode Minimum Depth of Binary Tree

111. 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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.


求一棵二叉树的最小深度,类似于LeetCode Maximum Depth of Binary Tree求最大深度,但是稍微难一点。 请注意,不能直接把求最大深度的大于号改为小于号:

class Solution {
public:
    int dfs(TreeNode* root, int nDepth)
    {
        if (root == NULL)
            return nDepth;
        int left = dfs(root->left, nDepth + 1);
        int right = dfs(root->right, nDepth + 1);
        return left < right ? left : right;
    }
    int minDepth(TreeNode* root) { return dfs(root, 0); }
};

因为如上图所示,当走到A点时,没有右孩子,导致int right = dfs(root->right, nDepth + 1);会得到A点的高度2,比左孩子的高度低,即最小高度为2了。但是最小高度显然是4。所以需要稍加修改,使得如果某个孩子为空时,不在该孩子深搜了,只有当两个孩子都为空时(即是叶子节点时),才得到一个合法的深度,去和其他深度做比较。

深度搜索的完整代码如下:

class Solution {
public:
    int dfs(TreeNode* root, int nDepth)
    {
        if (root == NULL)
            return nDepth;
        if (root->left == NULL && root->right == NULL)
            return nDepth + 1;
        int left = root->left == NULL ? INT_MAX : dfs(root->left, nDepth + 1);
        int right = root->right == NULL ? INT_MAX : dfs(root->right, nDepth + 1);
        return left < right ? left : right;
    }
    int minDepth(TreeNode* root) { return dfs(root, 0); }
};

本代码提交AC,用时9MS。
但是DFS必须走到所有叶子节点才能得到最小深度,而如果采用广度优先搜索BFS时,遇到的第一个叶子节点的深度就是最小深度了,就可以返回了。所以理论上,BFS的性能会更优。
BFS的完整代码如下:

struct NewTreeNode {
    TreeNode* tn;
    int depth;
};
class Solution {
public:
    int bfs(TreeNode* root)
    {
        queue<NewTreeNode*> qTree;
        NewTreeNode* ntn = new NewTreeNode;
        ntn->tn = root;
        ntn->depth = 0;
        qTree.push(ntn);
        NewTreeNode* top = new NewTreeNode;
        while (!qTree.empty()) {
            top = qTree.front();
            qTree.pop();
            if (top->tn == NULL)
                return top->depth;
            if (top->tn->left == NULL && top->tn->right == NULL)
                return top->depth + 1;
            if (top->tn->left != NULL) {
                NewTreeNode* tmp = new NewTreeNode;
                tmp->tn = top->tn->left;
                tmp->depth = top->depth + 1;
                qTree.push(tmp);
            }
            if (top->tn->right != NULL) {
                NewTreeNode* tmp = new NewTreeNode;
                tmp->tn = top->tn->right;
                tmp->depth = top->depth + 1;
                qTree.push(tmp);
            }
        }
        return -1;
    }
    int minDepth(TreeNode* root) { return bfs(root); }
};

本代码提交AC,用时也是9MS。
我看Leetcode上有很多关于树的题,为了方便测试,自己写了一个由数组构造树结构的函数,如下:

#include <vector>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
        : val(x)
        , left(NULL)
        , right(NULL)
    {
    }
};
TreeNode* genTree(vector<int>& vi, int id)
{
    if (vi.size() == 0)
        return NULL;
    TreeNode* root = new TreeNode(vi[id]);
    if (2 * id + 1 < vi.size() && vi[2 * id + 1] != -1) {
        root->left = genTree(vi, 2 * id + 1);
    }
    if (2 * id + 2 < vi.size() && vi[2 * id + 2] != -1) {
        root->right = genTree(vi, 2 * id + 2);
    }
    return root;
}
int main()
{
    vector<int> vTree = { 1, 2, 3, 4, 5 };
    TreeNode* root = genTree(vTree, 0);
    return 0;
}

使用时只要传入数组和0,返回的就是一个建好的树。用数组存树,一般第i号节点的左右孩子下标分别为2i+1和2i+2。存好之后恰好是一棵树的层次遍历结果。
如果要构建的不是一棵完全树,比如下面的左图,则先需要转换为完全图,也就是用-1代替一个不存在的节点,此时传入的数组应该是[1,-1,2,-1,-1,3,-1],genTree函数遇到-1会自动跳过不创建节点。当然如果你的树中本来就有-1这个值,也可以把-1换成其他数。

二刷。BFS的代码还可以写得更简洁漂亮一些,类似于层次遍历,遍历到某一层有叶子节点时,层数就是最小深度,代码如下:

class Solution {
public:
    int minDepth(TreeNode* root)
    {
        if (root == NULL)
            return 0;
        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            ++depth;
            int n = q.size();
            while (n--) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur->left == NULL && cur->right == NULL)
                    return depth;
                if (cur->left != NULL)
                    q.push(cur->left);
                if (cur->right != NULL)
                    q.push(cur->right);
            }
        }
        return depth;
    }
};

本代码提交AC,用时9MS。
DFS的代码也可以写得更漂亮一些:

class Solution {
public:
    int minDepth(TreeNode* root)
    {
        if (root == NULL)
            return 0;
        if (root->left == NULL)
            return minDepth(root->right) + 1;
        if (root->right == NULL)
            return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

本代码提交AC,用时13MS,比BFS慢。

LeetCode Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.


计算出二叉树的最大深度,简单题,直接深搜即可。。。 完整代码如下:

class Solution {
public:
    int dfs(TreeNode* root, int nDepth)
    {
        if (root == NULL)
            return nDepth;
        int left = dfs(root->left, nDepth + 1);
        int right = dfs(root->right, nDepth + 1);
        return left > right ? left : right;
    }
    int maxDepth(TreeNode* root) { return dfs(root, 0); }
};


本代码提交AC,用时13MS。
二刷。还可以更简洁一些:

class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if (root == NULL)
            return 0;
        if (root->left == NULL && root->right == NULL)
            return 1;
        int left_depth = maxDepth(root->left), right_depth = maxDepth(root->right);
        return max(left_depth, right_depth) + 1;
    }
};

本代码提交AC,用时6MS。

LeetCode Unique Paths II

63. Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

承接LeetCode Unique Paths,只是把网格中设置了障碍,第一思路是DFS,如果下一步能走,则递归深入搜索,否则返回。完整代码如下:

class Solution {
public:
    void dfs(vector<vector<int> >& obstacleGrid, int x, int y, int& numPath)
    {
        if (obstacleGrid[x][y] == 1)
            return;
        if (x == obstacleGrid.size() – 1 && y == obstacleGrid[0].size() – 1)
            numPath++;
        else {
            if (y + 1 < obstacleGrid[0].size())
                dfs(obstacleGrid, x, y + 1, numPath);
            if (x + 1 < obstacleGrid.size())
                dfs(obstacleGrid, x + 1, y, numPath);
        }
    }
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
    {
        int numPath = 0;
        dfs(obstacleGrid, 0, 0, numPath);
        return numPath;
    }
};

但是TLE失败:-(

查题解,恍然大悟,DP解决。设dp[j]为从左上角到obstacleGrid[i][j]共有多少种方案,如果obstacleGrid[i][j]==1,则不可能到达这一点,dp[j]=0;否则,可以从[i][j-1]和[i-1][j]两个点到达[i][j],即dp[j]=dp[j]+dp[j-1]。因为只用了一个数组保存中间结果,所以右边的dp[j]相当于dp[i-1][j],dp[j-1]相当于dp[i][j-1],左边的dp[j]才是dp[i][j]。
$$dp[i][j]=\begin{cases}0\quad\text{if obstacleGrid[i][j]==1}\\dp[i-1][j]+dp[i][j-1]\quad\text{otherwise}\end{cases}$$

完整代码如下:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
    {
        vector<int> dp(obstacleGrid[0].size(), 0);
        if (obstacleGrid[0][0] == 0)
            dp[0] = 1; // caution!
        for (int i = 0; i < obstacleGrid.size(); i++) {
            for (int j = 0; j < obstacleGrid[i].size(); j++) {
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else
                    dp[j] += j == 0 ? 0 : dp[j – 1];
            }
        }
        return dp[obstacleGrid[0].size() - 1];
    }
};

本代码提交AC,用时6MS。

LeetCode Combination Sum II

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

这题和之前的LeetCode Combination Sum很类似,但是要求同一个数字不能重复选,不过candidates里面可能会有重复的数字。所以策略就是在一个for循环里面判断数字是否重复,注意不能在递归里面判断所选数字是否重复,因为递归的时候是可以选相同数字的,比如样例的[1,1,6]。同时递归的时候传入当前下标的下一个下标。
完整代码如下:

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidates, int idx, vector<int>& sol, int target)
    {
        if (target == 0) {
            ans.push_back(sol);
        }
        else {
            for (int i = idx; i < candidates.size(); i++) {
                if (candidates[i] > target)
                    break;
                if (i != idx && candidates[i] == candidates[i – 1])
                    continue; // i != idx
                sol.push_back(candidates[i]);
                work(ans, candidates, i + 1, sol, target – candidates[i]); // i + 1
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int>& candidates, int target)
    {
        vector<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, 0, sol, target);
        return ans;
    }
};

本代码提交AC,用时10MS。

二刷。相比于LeetCode Combination Sum,这一题确实需要对输入数组排序,与上述解法类似,代码如下:

class Solution {
public:
	void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
		if (target == 0) {
			ans.push_back(cur);
			return;
		}
		if (target < 0)return;
		int i = idx;
		while (i < candidates.size()) {
			if (i > idx&&candidates[i] == candidates[i - 1]) {
				++i;
				continue;
			}
			target -= candidates[i];
			cur.push_back(candidates[i]);
			dfs(candidates, target, ans, cur, i + 1);
			target += candidates[i];
			cur.pop_back();
			++i;
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> cur;
		sort(candidates.begin(), candidates.end());
		dfs(candidates, target, ans, cur, 0);
		return  ans;
	}
};

本代码提交AC,用时8MS。

LeetCode Combination Sum

39. Combination Sum

Given a set of candidate numbers (candidates(without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

本题要从一个集合中取出一些数,使得和为某个特定的数target,输出所有的这种组合。注意不能有重复的组合,比如[2,2,3]和[3,2,2]算是重复的。

这是很常见的组合问题,使用递归的思路求解。比如样例,要求和为7,则每个加数必须小于等于7,所以依次尝试2,3,6,7,如果是2,则还差7-2=5,所以递归的在[2,3,6,7]里面找和为5的组合。如此递归,直到差为0。但是这样有一个问题,比如你这一次尝试的是2,则可能得到[2,2,3]的组合,下一次尝试3,则可能得到[3,2,2]的组合,但是这两个组合是相同的。我一开始的想法是对组合排序,然后用set去重。代码如下:

class Solution {
public:
    void work(set<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
    {
        if (target == 0) {
            vector<int> tmp = sol;
            sort(tmp.begin(), tmp.end());
            ans.insert(tmp);
        }
        else {
            for (int i = 0; i < candidates.size(); i++) {
                if (candidates[i] > target)
                    break;
                sol.push_back(candidates[i]);
                work(ans, candidates, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        set<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, sol, target);
        return vector<vector<int> >(ans.begin(), ans.end());
    }
};


本代码提交AC,但是用时145MS,只击败了4.5%的人,所以肯定还有更优的方案。

上述方案的一个费时的地方就是要对每个组合排序,然后用set去重,如果能省掉这个环节,速度会快很多。

网上查看题解之后,恍然大悟,每次只选不小于上一次选过的数,这样得到的组合就不会有重复,不需要排序,也不需要set去重。比如上面的例子,在选到3时,差7-3=4,此时再从[2,3,6,7]里面选时,只选大于等于3的数,也就是3,6,7,不再考虑2了。但是6,7都大于4,不行;3的话,剩余4-3=1也无解。所以搜3的时候,就不会得到[3,2,2]的结果,也就无需去重。
完整代码如下:

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
    {
        if (target == 0) {
            ans.push_back(sol);
        }
        else {
            for (int i = 0; i < candidates.size(); i++) {
                if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() – 1]))
                    continue;
                sol.push_back(candidates[i]);
                work(ans, candidates, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, sol, target);
        return ans;
    }
};

本代码提交AC,用时20MS,速度快了好多。

后来我发现这个版本的代码还可以优化,因为candidates已经排好序了,如果这次取了i号元素,下一次只要取i及以后的元素即可,所以在递归的时候多传入一个下标值,也能提速。完整代码如下:

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidates, int idx, vector<int>& sol, int target)
    {
        if (target == 0) {
            ans.push_back(sol);
        }
        else {
            for (int i = idx; i < candidates.size(); i++) {
                if (candidates[i] > target)
                    break;
                sol.push_back(candidates[i]);
                work(ans, candidates, i, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, 0, sol, target);
        return ans;
    }
};

本代码提交AC,用时16MS。

二刷。没必要排序,直接DFS选当前及后续元素即可,代码如下:

class Solution {
public:
	void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
		if (target == 0) {
			ans.push_back(cur);
			return;
		}
		if (target < 0)return;
		for (int i = idx; i < candidates.size(); ++i) {
			target -= candidates[i];
			cur.push_back(candidates[i]);
			dfs(candidates, target, ans, cur, i);
			cur.pop_back();
			target += candidates[i];
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> cur;
		dfs(candidates, target, ans, cur, 0);
		return ans;
	}
};

本代码提交AC,用时12MS。

LeetCode Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.


给定一串手机按键数字序列,要求给出所有可能的字符串组合。本题实质是一个搜索问题,DFS算法如下:

class Solution {
public:
    void dfs(string& digits, int step, vector<string>& alphabeta, vector<string>& ans, bool is_first)
    {
        if (step == digits.size())
            return;
        string cur = alphabeta[digits[step] – ‘0’];
        if (is_first) {
            for (int i = 0; i < cur.size(); i++)
                ans.push_back(cur.substr(i, 1));
            is_first = false;
        }
        else {
            int sz = ans.size(); //size要提前抽出来
            for (int i = 0; i < sz; i++) {
                string tmp = ans[i];
                ans[i] = ans[i] + cur.substr(0, 1);
                for (int j = 1; j < cur.size(); j++)
                    ans.push_back(tmp + cur.substr(j, 1));
            }
        }
        dfs(digits, step + 1, alphabeta, ans, is_first);
    }
    vector<string> letterCombinations(string digits)
    {
        vector<string> alphabeta = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        vector<string> ans;
        dfs(digits, 0, alphabeta, ans, true);
        return ans;
    }
};

本代码提交AC,用时0MS。
本题当然也可以用BFS做。

二刷:
原来解法有一个is_first,而且for循环里处理不够优雅,这一题明显可以用一种更漂亮、统一的方法,代码如下:

class Solution {
private:
    void dfs(string& digits, int step, vector<string>& alphabeta, vector<string>& ans, string& candidate)
    {
        if (step == digits.size()) {
            ans.push_back(candidate);
            return;
        }
        int idx = digits[step] – ‘0’;
        for (int i = 0; i < alphabeta[idx].size(); ++i) {
            candidate.push_back(alphabeta[idx][i]);
            dfs(digits, step + 1, alphabeta, ans, candidate);
            candidate.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits == "")
            return {};
        vector<string> alphabeta = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        vector<string> ans;
        string candidate = "";
        dfs(digits, 0, alphabeta, ans, candidate);
        return ans;
    }
};

本代码提交AC,用时0MS。

hihoCoder 1087 & week 63-1-Hamiltonian Cycle

hihoCoder 1087 & week 63-1-Hamiltonian Cycle #1087 : Hamiltonian Cycle 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Given a directed graph containing n vertice (numbered from 1 to n) and m edges. Can you tell us how many different Hamiltonian Cycles are there in this graph? A Hamiltonian Cycle is a cycle that starts from some vertex, visits each vertex (except for the start vertex) exactly once, and finally ends at the start vertex. Two Hamiltonian Cycles C1, C2 are different if and only if there exists some vertex i that, the next vertex of vertex i in C1 is different from the next vertex of vertex i in C2. 输入 The first line contains two integers n and m. 2 <= n <= 12, 1 <= m <= 200. Then follows m line. Each line contains two different integers a and b, indicating there is an directed edge from vertex a to vertex b. 输出 Output an integer in a single line — the number of different Hamiltonian Cycles in this graph. 提示 额外的样例:

样例输入 样例输出
3 3 1 2 2 1 1 3 0
样例输入 4 7 1 2 2 3 3 4 4 1 1 3 4 2 2 1 样例输出 2
本题要求解一个有向图中存在多少个哈密顿回路,因为本题的n不超过12,所以可以暴力求解,但是可以用位运算和记忆化搜索提高搜索速度。 常规思路是从某一点DFS,计算所有哈密顿回路的数量,伪代码如下: [cpp] DFS(int nowVertex, bool visitedVertex, int path, int length) visitedVertex[ nowVertex ] = True; If (all Vertex is visited) Then Count = Count + 1 Else For (u is next vertex of nowVertex) If (not visitedVertex[ u ]) Then path[ length ] = u DFS(u, visitedVertex, path, length + 1) End If End For End If visitedVertex[ nowVertex ] = False [/cpp] 位运算的思路是用变量unused的二进制位表示一个点是否访问过,1未访问,0访问了。所以当DFS到unused==0时,找到一条哈密顿路径,如果该路径的终点能回到起点(默认为1),则构成一条哈密顿回路。部分代码如下: [cpp] const int MAXN = 14; int edge[ MAXN ];//edge[i]二进制中1的序号表示i能访问的节点编号 int p[1 << MAXN];//p[1<<i]=i+1表示只有i点访问了的情况为1<<i int cnt; void dfs(int nowVertex, int unused) { if (!unused) {//所有节点访问完了 cnt += (edge[nowVertex] & 1);//判断能否回到起始节点1 return ; } int rest = unused & edge[ nowVertex ];//剩余的能访问到的未访问节点 while (rest) { int tp = rest & (-rest);//依次取出可访问节点 dfs(p[ tp ], unused – tp);//访问 rest -= tp; } return ; } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[ 1 << i ] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1);//记录u能访问节点的情况 } dfs(1, (1 << n) – 2);//初始的时候访问了1号节点,所以-1-1=-2 printf("%d\n", cnt); return 0; } [/cpp] 这一版本的代码简洁易懂,效率也还可以,用时558MS,内存0MB。 但是还可以改进,在DFS过程中可能遇到某个节点的多次unused相同的情况,此时后面几次的DFS都是没有必要的,可以剪枝。 设f[i][j]为当前访问节点为i,已经访问过的节点情况为j时的方案数,则哈密顿路径的情况数为f[i][0],i在[1,n],哈密顿回路的情况数就是把所有i能回到1的f[i][0]情况数加起来。 那么怎么来计算f[i][j]呢,需要按照状态中1的个数来枚举,伪代码如下: [cpp] For numberOfOnes = n-1 .. 0 For (unused | the number of ones of unused equals numberOfOnes) For nowVertex = 1 .. n For prevVertex = 1 .. n If (unused & (1 << (nowVertex – 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex – 1)) != 0) Then f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex – 1))] End If End For End For End For End For [/cpp] 第二层for循环中的unused就是所有“在n位二进制中设置numberOfOnes位1”的所有状态,最内层的if判断该状态必须满足1)已经访问了当前节点2)前驱节点不等于当前节点3)前驱节点有到当前节点的边,则f[当前节点][访问情况为unused]+=f[前驱节点][访问情况为unused+还没访问当前节点]。 详细分析可以看官方题解。完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<vector> #include<iterator> using namespace std; const int MAXN = 14; int edge[MAXN]; int p[1 << MAXN]; int f[MAXN][1<<MAXN]; //n位二进制中出现k个1的所有排列情况 vector<int> dfs(int n, int k) { if (k == 0)//出现0个1,只有一种情况,全0 return vector<int>(1, 0); else { //********** n==k的情况 ************************** vector<int> r = dfs(n – 1, k – 1);//n-1位中出现k-1个1//将大问题分解成小问题 for (int &i : r) { i |= (1 << (n – 1));//补上第n位也为1 } //************************************************** if (n > k) { vector<int> t = dfs(n – 1, k);//此时第n位可以为0 copy(t.begin(), t.end(), back_inserter(r)); } return r; } } int main() { //freopen("input.txt", "r", stdin); int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[1 << i] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1); } f[1][(1 << n) – 2] = 1; for (int numberOfOnes = n – 1; numberOfOnes >= 0; numberOfOnes–) { vector<int> stat = dfs(n, numberOfOnes); for (int i = 0; i < stat.size(); i++) { int s = stat[i]; for (int nowVertex = 1; nowVertex <= n; nowVertex++) { for (int prevVertex = 1; prevVertex <= n; prevVertex++) { if ((s & (1 << (nowVertex – 1))) == 0 && prevVertex != nowVertex && (edge[prevVertex] & (1 << (nowVertex – 1))) != 0) f[nowVertex][s] += f[prevVertex][s | (1 << (nowVertex – 1))]; } } } } int cnt = 0; for (int i = 1; i <= n; i++) if (edge[i] & 1) cnt += f[i][0]; printf("%d\n", cnt); return 0; } [/cpp] 本代码提交AC,用时21MS,内存0MB,相比于上一版本,速度提升了一个数量级。]]>

HDOJ 5424-Rikka with Graph II

HDOJ 5424-Rikka with Graph II Rikka with Graph II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 379 Accepted Submission(s): 94 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path. It is too difficult for Rikka. Can you help her? Input There are no more than 100 testcases. For each testcase, the first line contains a number n(1≤n≤1000). Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. Output For each testcase, if there exist a Hamiltonian path print “YES” , otherwise print “NO”. Sample Input 4 1 1 1 2 2 3 2 4 3 1 2 2 3 3 1 Sample Output NO YES Hint For the second testcase, One of the path is 1->2->3 If you doesn’t know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path). Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422


这题题意很明确,判断一个无向图中是否存在哈密顿路径,注意不是哈密顿回路。
由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次,形成的路径称为哈密顿路径,闭合的哈密顿路径称作哈密顿回路,含有哈密顿回路的图称为哈密顿图。
本来判断一个常规图中是否存在哈密顿路径是NP完全问题,不可能有多项式解,所以如果依次对每个点DFS,肯定超时。 但是这题很特殊,图中只有n个点,n条边!如果存在哈密顿路径L,则路径长度为n-1条边,设L两个端点为A,B,此时还剩下一条边a,这条边有三种情况: 1)a在L的内部连接,这时A,B的度数都为1,其他点的度数为2或3; 2)a一端在A(或B),另一端在L的内部,这时L的另一个端点B(或A)的度数为1,其他点的度数为2或3; 3)a连接了A,B,此时所有点的度数都为2。 如果存在哈密顿路径,这三种情况下,L的某个端点的度数都是最少的。所以可以先找到度数最小的点,再从这个点开始DFS,这样只需要一次DFS就可以判断是否存在哈密顿路径。 当然要先判断这个图是否连通,我起初使用了并查集,但是超时,郁闷。后来发现,如果哈密顿路径存在,则肯定连通,且此时读数为1点不超过2个,所以可以用这个条件判断是否连通。 完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; const int kMaxN = 1005; int degree[kMaxN]; vector<vector<int>> path; int visit[kMaxN]; int n, done; bool DFS(int s) { done++; visit[s] = 1; if (done == n) return true; int v; for (int i = 0; i < path[s].size(); i++) { v = path[s][i]; if (!visit[v]) { if (DFS(v)) return true; } } done–; visit[s] = 0; return false; } bool CheckHamiltonian() { int min_degree = n + 1, bad_node_num = 0, id; for (int i = 1; i <= n; i++) { if (degree[i] && degree[i] < min_degree) { min_degree = degree[i]; id = i; } if (degree[i] <= 1) bad_node_num++; } if (bad_node_num > 2) return false; memset(visit, 0, sizeof(visit)); done = 0; return DFS(id); } int main() { //freopen("input.txt", "r", stdin); while (~scanf("%d", &n)) { memset(degree, 0, sizeof(degree)); path.clear(); path.resize(n + 1); int u, v; for (int i = 0; i < n; i++) { scanf("%d %d", &u, &v); if (u == v) continue; degree[u]++; degree[v]++; path[u].push_back(v); path[v].push_back(u); } if (CheckHamiltonian()) printf("YES\n"); else printf("NO\n"); } return 0; } [/cpp] 本代码提交AC,用时93MS,内存1800K。]]>

hihoCoder week 52-1-连通性·一

hihoCoder week 52-1-连通性·一 题目1 : 连通性·一 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 还记得上次小Hi和小Ho学校被黑客攻击的事情么,那一次攻击最后造成了学校网络数据的丢失。为了避免再次出现这样的情况,学校决定对校园网络进行重新设计。 学校现在一共拥有N台服务器(编号1..N)以及M条连接,保证了任意两台服务器之间都能够通过连接直接或者间接的数据通讯。 当发生黑客攻击时,学校会立刻切断网络中的一条连接或是立刻关闭一台服务器,使得整个网络被隔离成两个独立的部分。 举个例子,对于以下的网络: 每两个点之间至少有一条路径连通,当切断边(3,4)的时候,可以发现,整个网络被隔离为{1,2,3},{4,5,6}两个部分: 若关闭服务器3,则整个网络被隔离为{1,2},{4,5,6}两个部分: 小Hi和小Ho想要知道,在学校的网络中有哪些连接和哪些点被关闭后,能够使得整个网络被隔离为两个部分。 在上面的例子中,满足条件的有边(3,4),点3和点4。 提示:割边&割点 输入 第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000 第2..M+1行:2个正整数,u,v。表示存在一条边(u,v),连接了u,v两台服务器。1≤u<v≤N 保证输入所有点之间至少有一条连通路径。 输出 第1行:若干整数,用空格隔开,表示满足要求的服务器编号。从小到大排列。若没有满足要求的点,该行输出Null 第2..k行:每行2个整数,(u,v)表示满足要求的边,u<v。所有边根据u的大小排序,u小的排在前,当u相同时,v小的排在前面。若没有满足要求的边,则不输出 样例输入 6 7 1 2 1 3 2 3 3 4 4 5 4 6 5 6 样例输出 3 4 3 4


本题要求一个连通图的割边和割点,使用Tarjan算法,提示已经把dfs主要代码写了,完善一下即可。 主要要理解上面的递推公式。首先理解dfn和low的含义,dfn[u]记录节点u在DFS过程中被遍历到的次序号,low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次序号最小)。 上图的第一个式子,当(u,v)为树边时,low[u]表明u能追溯到的最早节点,low[v]表明u的子树(v就是u的子树的根)能追溯到的最早节点,所以根据low[u]的定义有low[u]=min(low[u],low[v])。 上图的第二个式子,当(u,v)为回边时,因为low[u]的定义就是u通过非父子边(回边)追溯最早的节点,所以既然(u,v)为回边,自然的low[u]=min(low[u],dfn[v])。 另外注意输出格式,点要从小到大排列;边(u,v)保证u<v,以u从小到大排列,再以v从小到大排列。完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<set> #include<algorithm> #include<vector> using namespace std; const int kMaxN = 20005; int n, m; typedef struct edge { int x, y; bool operator<(const edge& p)const//如果要加入到set中,需要重载< { return (this->x<p.x) || ((this->x == p.x) && (this->y<p.y)); } }; set<int> points; set<edge> edges; vector<vector<int>> graph; int visit[kMaxN]; int dfn[kMaxN]; int low[kMaxN]; int parent[kMaxN]; void dfs(int u) { //记录dfs遍历次序 static int counter = 0; //记录节点u的子树数 int children = 0; visit[u] = 1; //初始化dfn与low dfn[u] = low[u] = ++counter; for (int i = 0; i < graph[u].size();i++) { int v = graph[u][i]; //节点v未被访问,则(u,v)为树边 if (visit[v]==0) { children++; parent[v] = u; dfs(v); low[u] = min(low[u], low[v]); //case (1) if (parent[u] == 0 && children > 1) { points.insert(u); } //case (2) if (parent[u] != 0 && low[v] >= dfn[u]) { points.insert(u); } //bridge if (low[v] > dfn[u]) { edge e; e.x = u; e.y = v; if (u > v) { e.x = v; e.y = u; } edges.insert(e); } } //节点v已访问,则(u,v)为回边 else if (v != parent[u]) { low[u] = min(low[u], dfn[v]); } } } int main() { scanf("%d %d", &n, &m); graph.resize(n + 1); int u, v; while (m–) { scanf("%d %d", &u, &v); graph[u].push_back(v); graph[v].push_back(u); } dfs(1); if (points.size() == 0) printf("Null\n"); else { set<int>::iterator it = points.begin(); while (it != points.end()) { printf("%d ", *it); it++; } printf("\n"); } if (edges.size() > 0) { set<edge>::iterator it = edges.begin(); while (it != edges.end()) { printf("%d %d\n", (*it).x, (*it).y); it++; } } return 0; } [/cpp] 本代码提交AC,用时76MS,内存7MB。]]>