重返天梯-关于树的深搜

文章目录

• DFS搜树
• L2-031-深入虎穴
• • 题目描述
  • C++
• L2-038-病毒溯源
• • 题目描述
  • C++

DFS搜树

这类题属于dfs搜树类型的题，所以放在了一起，便于复习巩固

AcWing 4310. 树的DFS-codeslogan

L2-031-深入虎穴 题目描述

简言之，找到树的最长链的最后一个结点

这道题出简单了，题目保证这样的结点只有一个

C++

#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
bool st[N];
int maxl = -1e9, ans;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int len) {
    if (len > maxl) {
        ans = u;
        maxl = len;
    }
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j, len + 1);
    }
}

int main() {
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            add(i, x);
            st[x] = true;
        }
    }
    
    int root = 1;
    while (st[root]) root++;
    dfs(root, 1);
    cout << ans << endl;

    return 0;
}

L2-038-病毒溯源 题目描述

简言之，按照字典序遍历树的结点，同时记录下最长链及其结点

由于是字典序，想到用vector根据双亲表示法对数据进行存储

利用深搜确定最长链

原题链接

C++

#include 
using namespace std;
const int N = 1e4 + 10;
vector<int> v[N];
int n;
int maxl = -1e9;
int ans[N];
bool st[N];

int dfs(int u) {
    int res = 0;
    for (int i = 0; i < v[u].size(); i++) {
        int d = dfs(v[u][i]);
        
        if (d > res) {
            res = d;
            ans[u] = v[u][i];
        }
    }
    return res + 1;
}


int main() {
    memset(ans, -1, sizeof ans);
    
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            v[i].push_back(x);
            st[x] = true;
        }
    }
    
    for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end());
    
    int root = 0;
    while (st[root]) root++;
    
    maxl = dfs(root);
    
    cout << maxl << endl;
    cout << root;
    
    while (ans[root] != -1) {
        cout << " " << ans[root];
        root = ans[root];
    }
    
    return 0;
}

虽然最后写了出来，但能够感觉到自己的熟练度还是不够，细节上还是想了很久