题目描述

环形树求深度

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 1010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int d[N];

vector<int> cirs;
stack<int> path;

//连一条从a指向b的边
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

bool dfs_cir(int u, int p) //p表示它的父亲
{
    st[u] = true; //这个点已经被访问过了
    path.push(u);

    //遍历当前点的所有子节点
    for (int i = h[u]; ~i; i = ne[i]) //~i == i >= 0
    {
        int j = e[i];

        if (j != p)
        {
            if (st[j])
            {
                //找出环上的所有点
                while (path.top() != j)
                {
                    cirs.push_back(path.top());
                    path.pop();
                }

                cirs.push_back(j);

                return true;
            }

            if (dfs_cir(j, u)) return true; //从递归中退出
        }
    }

    path.pop();

    return false;
}

void dfs_dep(int u, int depth)
{
    st[u] = true;
    d[u] = depth;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
            dfs_dep(j, depth + 1);
    }
}

int main()
{
    int T;
    cin >> T;

    for (int C = 1; C <= T; C ++)
    {
        cin >> n;

        //邻接表需要初始化为空
        memset(h, -1, sizeof h);
        //邻接表内存池下标
        idx = 0;
        memset(st, 0, sizeof st);
        cirs.clear();
        //stack没有clear,需要重新构造一遍
        path = stack<int>();

        for (int i = 0; i < n; i ++)
        {
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
        }

        dfs_cir(1, -1);//记录一下从哪个边过来的 防止原路返回

        memset(st, 0, sizeof st);

        for (auto c : cirs) st[c] = true;
        for (auto c : cirs) dfs_dep(c, 0);

        printf("Case #%d:", C);
        for (int i = 1; i <= n; i ++) printf(" %d", d[i]);
        puts("");
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla