L2-031 深入虎穴 (25 分)

题目

题目说明没有两个路通往一扇门，说明没有环，这是一棵树。问题转化为求树的深度。

思路

由于树的特性，我们可以通过深度优先搜索（DFS）来计算每个节点的深度。为了提高效率，我们采用从叶子节点开始的DFS，加上剪枝技术，避免重复计算深度。剪枝技术的具体实现是：一旦发现某条路径的深度已经达到最大值，就停止进一步的DFS探索。

代码实现了从根节点开始的DFS，记录每个节点的深度值。在计算过程中，采用简单的剪枝技术，避免了不必要的重复计算，确保算法的高效性。

代码

```cpp #include

#include

using namespace std;

#define INF 0x3f3f3f3f3f3f

#define pb push_back

typedef pair<int, int> P;

const int N = 1e5 + 10;

typedef long long ll;

vector<vector

> pre(N);

bool vis[N];

int num[N];

int dfs(int u) {

if (num[u]) return num[u];

if (!pre[u].empty()) return 0;

int max_depth = 0;

for (auto v : pre[u]) {

if (!vis[v]) {

vis[v] = true;

int d = dfs(v);

if (d > max_depth) max_depth = d;

}

num[u] = max_depth + 1;

return max_depth + 1;

}

int main() {

int n;

cin >> n;

for (int i = 1; i <= n; ++i) {

int m;

cin >> m;

for (int j = 1; j <= m; ++j) {

int x;

cin >> x;

pre[x].pb(i);

vis[x] = true;

}

int max_depth = -1;  int root = -1;  for (int i = 1; i <= n; ++i) {      if (!vis[i]) {          int d = dfs(i);          if (d > max_depth) {              max_depth = d;              root = i;          }      }  }  cout << root << endl;  return 0;

}

转载地址：http://cpwzz.baihongyu.com/

你可能感兴趣的文章