CCF-CSP题解 201503-4 网络延时

求树的直径。

两遍\(dfs\)就好了。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

const int maxn = 10000;

const int maxm = 10000;

using namespace std;

int to[(maxn + maxm) * 2 + 10];

int nex[(maxn + maxm) * 2 + 10];

int head[maxn + maxm + 10], cnt = 0;

void addEdge(int a, int b)

{

    to[cnt] = b; nex[cnt] = head[a]; head[a] = cnt++;

    to[cnt] = a; nex[cnt] = head[b]; head[b] = cnt++;

}

int ans, depth;

void dfs(int x, int f, int d)

{

    if (d > depth)

        ans = x, depth = d;

    for (int i = head[x]; i != -1; i = nex[i])

    {

        int l = to[i];

        if (l != f)

            dfs(l, x, d + 1);

    }

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    memset(head, -1, sizeof(head));

    for (int i = 2, temp; i <= n; i++)

    {

        scanf("%d", &temp);

        addEdge(i, temp);

    }

    for (int i = 1, temp; i <= m; i++)

    {

        scanf("%d", &temp);

        addEdge(i + n, temp);

    }

    ans = depth = -1;

    dfs(1, 1, 0);

    depth = -1;

    dfs(ans, ans, 0);

    printf("%d\n", depth);

    return 0;

}

巴特西

CCF-CSP题解 201503-4 网络延时

最新文章

热门文章