一、冗余连接
1、题目描述
树可以看成是一个连通且无环的无向图。给定一个图，该图从一棵 n 个节点（节点值 1～n）的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
2、思路
遍历每一条边，在加入这条边之前，先用 DFS/BFS 检测两个节点是否已经连通。如果已经连通，说明这条边就是多余的。
3、算法求解
（1）DFS做法
（主函数）
（DFS函数）
蓝桥杯必会写法：
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#define MAX_NODES 1005
// 初始化邻接矩阵（直接全局定义）
int adj[1001][1001];
bool canReachDFS(int curr, int target, bool* visited) {
// 找到了目标，返回 true
if (curr == target) return true;
// 标记当前节点已访问
visited[curr] = true;
// 遍历当前节点的所有邻居
for (int i = 1; i < 1001; i++) {
if (adj[curr][i] == 1) {
int neighbor = i;
// 如果邻居还没访问过，递归去查
if (!visited[neighbor]) {
if (canReachDFS(neighbor, target, visited)) {
return true;
}
}
}
}
return false;
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
int* result = (int*)malloc(2 * sizeof(int));
*returnSize = 2;
memset(adj, 0, sizeof(adj));
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0];
int v = edges[i][1];
// 每次 DFS 前重置 visited 数组
bool visited[MAX_NODES] = {false};
// 核心：用 DFS 检测 u 到 v 是否存在路径
if (canReachDFS(u, v, visited)) {
result[0] = u;
result[1] = v;
return result;
}
// 没连通，则加边
adj[u][v] = 1;
adj[v][u] = 1;
}
return result;
}（2）BFS做法
（主函数）
可见，BFS的逻辑和DFS的逻辑相同。
（BFS函数）
注意：要掌握BFS中队列的存储方法。
二、邻接表存储二叉树完整做法
