Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


烛昭

算法题:遍历树中m个点最少需要经过多少个结点

  给定一棵树,从树中任意结点出发,遍历m个结点,最少需要结果多少个结点,结点可以重复走。
  思路:找树中最长的链,也就是树的“直径”,假设为d,如果m小于等于d,则输出m就可以了;如果m大于d,则输出d+(m-d)*2,这是因为最长链上的分支路径需要走2遍(一来一回)。那么,直径也就是最长链怎么求?先从任意一个叶子节点x出发,找到最长的路径,假设路径结尾是y节点;再以y为根,找出最长的路径,这条路径就是树的最长路径。两次dfs可以搞定了。
  代码:

#include <iostream>
#include <vector>

using namespace std;

vector<int> vis;  
vector<vector<int>> tree;

pair<int, int> dfs(int x) {  
    int mx = 0;
    pair<int, int> ans;
    for (int i = 0; i < tree[x].size(); ++i) {
        if (!vis[tree[x][i]]) {
            vis[tree[x][i]] = 1;
            pair<int, int> ret = dfs(tree[x][i]);
            if (ret.first > mx) {
                mx = ret.first;
                ans = ret;
            }
        }
    }
    if (mx) {
        ++ans.first;
    }
    else {
        ans.second = x;
        ans.first = 1;
    }
    return ans;
}

int main() {  
    int n, k; // n: node, k: needed node
    int a, b;
    freopen("in.txt", "r", stdin);
    cin >> n >> k;
    tree.assign(n, vector<int>());
    vector<int> in(n, 0);
    vis.assign(n, 0);
    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
        ++in[a];
        ++in[b];
    }

    int root = 0;
    for (; root < n; ++root) {
        if (in[root] <= 1) {
            break;
        }
    }
    pair<int, int> firstRet = dfs(9);

    vis.assign(n, 0);
    pair<int, int> secondRet = dfs(firstRet.second);

    int len = secondRet.first;
    if (len >= k) {
        cout << k << endl;
    }
    else {
        cout << len + 2 * (k - len) << endl;
    }
}

About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus