大三实习，学校不让走怎么办？

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一同学在网上发文称，大三找到实习，学校不放，走不了，怎么办？结果在评论区发现还不止他一个人遇到这种情况。我记得学校不是挺看重就业率的吗，记得当年我毕业的时候，学校要求必须要签三方协议之后才能拿毕业证。现在学生找到工作又不让去实习，不知道学校咋想的？

不过我个人觉得这事不要和学校说，直接走就是了，如果学校要求必须回来到时候再回来，因为有些事不能问，一问就是不行，但你如果真做了实际上也没事。这就好比参加学校运动会一样，如果直接问辅导员我不参加行吗？那肯定是不行的，但你如果真的不去实际上也没事。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LintCode的第3890题：无向图中到环的距离。

问题描述

来源：LintCode第3890题

难度：困难

给定一个正整数 n，表示一个连通无向图中的节点数，节点编号为 0 到 n - 1，该图只包含一个环。

再给定一个二维整数数组 edges，其中 edges[i] = [node1, node2] 表示第 i 条边是一条双向连接了两个节点 node1 和 node2 的边。

两个节点 a 和 b 的距离定义为 节点 a 到节点 b 所需要的最少边数，返回一个长度为 n 的整数数组 res，求出图中所有节点到这个环的距离，即 res[i] 表示节点 i 到环中节点所需要的最少边数。

示例1：

输入： n = 7 edges = [[1, 2], [2, 4], [4, 3], [3, 1], [0, 1], [5, 2], [6, 5]] 输出： [1, 0, 0, 0, 0, 1, 2] 解释： 如下图 节点 1 - 4 构成了一个环，节点已经在环内，因此距离为 0 节点 0 到环的最小距离为 1 节点 5 到环的最小距离为 1 节点 6 到环的最小距离为 2

示例2：

输入： n = 6 egdes = [[0, 1], [1, 2], [0, 2], [0, 3], [3, 4], [3, 5]] 输出： [0, 0, 0, 1, 2, 2] 解释： 如下图 节点 0 - 2 构成了一个环，距离为 0 节点 3 到环的最小距离为 1 节点 4 到环的最小距离为 2 节点 5 到环的最小距离为 2

• 3≤n≤10^5

• 图是连通的

• 图仅有一个环

• 任何节点之间最多只有一条边

问题分析

这题说的是给定一个无向图，图中有且只有一个环，计算所有顶点到环的最短距离。 这题我们可以使用 ，拓扑排序需要是无环图，而这里是有环的，实际上没有影响。

我们首先按照拓扑排序的思路把所有 度为 1 的顶点全部添加到队列中 ，然后遍历队列中的顶点，当队列中的顶点 i 出队之后，和 i 相连的顶点 j 要把顶点 i 给移除，如果移除之后，顶点 j 的度也为 1 ，就把顶点 j 也添加到队列中 。

因为在 环中的所有顶点至少有两个度 ，所以除了环中的顶点，其它所有顶点都会入队和出队，这里我们还需要使用一个栈来记录出队的顺序，也就是 每个顶点的上游顶点 。比如示例 1 中 5 是 6 的上游顶点，最后计算距离的时候先计算顶点 5 在计算顶点 6 。

最后入栈的顶点肯定是和环挨着的，所以我们需要先计算和环挨着的顶点，然后一步步往外扩散，类似与从环开始进行BFS计算。

JAVA：

public int[] distanceToCycle(int n, int[][] edges) {
    // 把二维数组转成邻接表
    Set
       
       
 [] g =  new Set[n];     Arrays.setAll(g, k ->  new HashSet<>());      for ( int e[] : edges) {         g[e[ 0]].add(e[ 1]);         g[e[ 1]].add(e[ 0]);     }     Queue  q =  new ArrayDeque<>();      for ( int i =  0; i < n; i++) {          if (g[i].size() ==  1) // 把度为 1 的顶点添加到队列中             q.offer(i);     }      int[] parent =  new  int[n]; // 记录拓扑排序中的上游顶点     Stack  stk =  new Stack<>();      while (!q.isEmpty()) {          int i = q.poll();         stk.push(i); // 顶点 i 压栈。          for ( int j : g[i]) {             g[j].remove(i);             parent[i] = j; // 记录 i 的上游顶点是 j              // 移除 i 之后，如果顶点 j 的度为 1 ，把顶点 j 添加到队列中。              if (g[j].size() ==  1)                 q.offer(j);         }     }      int[] res =  new  int[n];      while (!stk.isEmpty()) {          int i = stk.pop(); // 先出栈的是和环挨着的，最后出栈的是离环最远的。         res[i] = res[parent[i]] +  1;     }      return res; }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。