2021天梯L2-2 病毒溯源

题目大意

给你多棵树，求树中最长链，如果长度相同，输出字典序最小的。

解题思路

绝了，比赛的时候都忘了拿啥记录路径了。。

题目本来很简单，就dfs加个记录路径即可。

保证字典序最小，可以用sort先排序，也可以用min比较vector（今天才知道。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
vector<int> v[N], ans, t;
int num[N], cnt = 0, c[N];


void dfs(int x) {
    if (!num[x]) {
        if (cnt < t.size()) {
            ans = t; cnt = t.size();
        }
        else if (cnt == t.size())    ans = min(ans, t);
    }
    for (auto p : v[x]) {
        t.push_back(p);
        dfs(p);
        t.pop_back();
    }
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        for (int j = 1; j <= num[i]; j++) {
            int x; cin >> x;
            c[x]++;
            v[i].push_back(x);
        }
        //sort(v[i].begin(), v[i].end());
    }
    for (int i = 0; i < n; i++) {
        if (!c[i]) {
            t.push_back(i);
            dfs(i);
            t.pop_back();
        }
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) {
        cout << ans[i];
        if (i != cnt - 1)   cout << ' ';
    }
}