P3465 病毒溯源

题目描述

给你一颗树，树中边权都是1，现在要求出从根结点出发，到所有叶子结点的最远距离，以及最远的路径。特别的：当最远距离相同时，按字典序比较具体路径，选择其中最小的。

Solution1 BFS

这是一个边权都是1的图，所以可以直接BFS搜索，每个点第一次被搜到时就是最短距离；先求出最长距离，之后排序求出所有最长路径中：字典序最小的路径。

时间复杂度：$O(n+m)$

C++ 代码

/*
等价于在边权都是1的树中找到最长的具体路径
*/
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4+10, M = 1e4+10;    //这里应该注意到每个结点有唯一的父结点，我们可以把边和孩子结点绑定，点数等于边数
int h[N], e[M], ne[M], idx;
int n;
int dis[N], Prev[N];
bool has[N];
int ans;
vector<vector<int>> res;

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    dis[u] = 1;
    while(q.size()){
        int t = q.front();
        q.pop();
        ans = max(ans, dis[t]);
        for(int i = h[t]; i!=-1; i=ne[i]){
            int j = e[i];
            q.push(j);
            //这里注意每个结点的父结点都是唯一的, 建的单向边, 所以不会重复遍历一个点
            dis[j] = dis[t]+1;
            Prev[j] = t;
        }
    }
}

void dfs(int u, vector<int> &temp)    //这里用引用参数，否则深层搜出的temp无法返回给上层
{
    if(Prev[u] == -1){
        temp.push_back(u);
    }
    else{
        dfs(Prev[u],temp);
        temp.push_back(u);
    }
    if(h[u] == -1){
        // for(int i = 0; i<temp.size(); ++i) cout << temp[i] << ' ';
        res.push_back(temp);
        // puts("");
    }

    return;
}

bool cmp(vector<int> a, vector<int> b)
{
    for(int i = 0; i<a.size(); ++i){
        if(a[i] != b[i]){
            return a[i] < b[i];
        }
    }
}

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

int main()
{
    memset(h, -1, sizeof h);
    memset(dis,0x3f,sizeof dis);
    memset(Prev, -1, sizeof Prev);
    scanf("%d", &n);
    for(int i = 0; i<n; ++i){
        int num;
        scanf("%d", &num);
        while(num--){
            int x;
            scanf("%d", &x);
            has[x] = true;
            add(i,x);
        }
    }
    int root = 0;
    for(int i = 0; i<n; ++i){
        if(!has[i] && h[i] != -1){
            root = i;
            break;
        }
    }

    bfs(root);
    cout << ans << endl;

    for(int i = 0; i<n; ++i){
        if(dis[i] == ans){
            vector<int> temp;
            dfs(i, temp);
        }
    }
    sort(res.begin(),res.end(), cmp);
    for(int i = 0; i<ans; ++i){
        if(i == 0) cout << res[0][0];
        else printf(" %d", res[0][i]);
    }
    return 0;
}

Solution2：DFS

1. 常规DFS记录树中各个点的深度当然可以直接：$d[son] = d[fa]+1$，但本题除了要保证距离最长外，还要字典序最小，这里字典序是从根结点向下找的，为了能直接求出这个字典序最小的路径，我们把深度计算换个方向，即计算各个结点到叶子结点的距离，每步转移时，先选距离最小的，当距离相等时，我们选择所有孩子结点中编号最小的。PS：如果正向计算深度，我们当然也可以选出每步编号最小的，但这样就不知道路径是不是最长的了。

时间复杂度$O(n+m)$

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4+10, M = 1e4+10;
int h[N], e[M], ne[M], idx;
int n;
bool st[N];
int son[N], ans;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    int res = 0;
    son[u] = -1;
    for(int i = h[u]; i!=-1; i=ne[i]){
        int j = e[i];
        int d = dfs(j);
        if(res < d){   //选择到叶子结点距离最大的分支
            res = d;
            son[u] = j;
        }
        else if(res == d && son[u] > j){    //当距离相等时选择编号最小的孩子结点转移
            son[u] = j;
        }
    }
    return res+1;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i<n; ++i){
        int num;
        cin >> num;
        while(num--){
            int x;
            cin >> x;
            st[x] = true;
            add(i,x);
        }
    }
    int root = 0;
    while(st[root]) root++;
    cout << dfs(root) << endl;
    for(int i = root; i!=-1; i=son[i]){
        if(i == root) cout << root;
        else printf(" %d", i);
    }
    return 0;
}