代码随想录算法训练营Day62|冗余连接、冗余连接II

冗余连接

108. 冗余连接 (kamacoder.com)

考虑使用并查集，逐次将s、t加入并查集中，当发现并查集中find(u)和find(v)相同时，输出u和v，表示删除的边即可。

#include 
#include 
using namespace std;
 
// 定义一个函数find，用于在并查集中找到元素u的根节点
int find(const vector<int>& check, int u) {
    if (u == check[u]) // 如果u是其自身的根，则返回u
        return u;
    else // 否则递归地查找u的根
        return find(check, check[u]);
}
// 定义一个函数join，用于合并两个集合
void join(vector<int>& check, int u, int v) {
    int n = find(check, u); // 找到u的根
    int m = find(check, v); // 找到v的根
    if (n == m) { // 如果两个根相同，说明加入边(u,v)会形成环
        cout << u << " " << v; // 输出这条边
    }
    check[m] = n; // 将v的根设置为u，实现集合的合并
}
 
int main() {
    int N;
    cin >> N; // 输入节点数和边数
    vector<int> check(N + 1, 0); // 初始化并查集数组
    for (int i = 0; i <= N; i++) {
        check[i] = i; // 每个元素的根初始化为自己
    }
    int s, t;
    for (int i = 0; i < N; i++) {
        cin >> s >> t; // 输入一条边的两个节点
        join(check, s, t); // 将两个节点合并到同一个集合中
    }
    return 0;
}

时间复杂度为O(N)，空间复杂度为O(N)。

冗余连接II

109. 冗余连接II (kamacoder.com)

代码随想录 (programmercarl.com)

本题本质为：一个有向图是由一颗有向树和一条有向边组成，我们需要找到并删除那条边。

此外，“若有多条边可以删除，请输出标准输入中最后出现的一条边”，说明在两条边都可以删除的情况下，要删除顺序靠后的边。

对于一颗有向树而言，根节点入度为0，其余节点入度为1。

因此对应的删除有三种情况：

1.有一点入度为2，删除指向该节点的一条边

3的入度为2，删除1->3或2->3。

2.入度为2，但只能删除特定边。

此处3的入度为2，但删除4->3明显无济于事，因此在找到入度为2的点还需判断删除哪条边会使图成为有向树。

3没有入度为2的点，有环。

只需删掉构成环的靠后的边即可。

贴一下代码随想录的代码：

#include 
#include 
using namespace std;
int n;
vector<int> father (1001, 0);
// 并查集初始化
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
 
// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vectorint>>& edges) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) { // 遍历所有的边
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
            cout << edges[i][0] << " " << edges[i][1];
            return;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}
 
// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vectorint>>& edges, int deleteEdge) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) {
        if (i == deleteEdge) continue;
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }
    return true;
}
 
int main() {
    int s, t;
    vectorint>> edges;
    cin >> n;
    vector<int> inDegree(n + 1, 0); // 记录节点入度
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edges.push_back({s, t});
    }
 
    vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
    // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
    for (int i = n - 1; i >= 0; i--) {
        if (inDegree[edges[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    if (vec.size() > 0) {
        // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
        if (isTreeAfterRemoveEdge(edges, vec[0])) {
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
        } else {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
        }
        return 0;
    }
 
    // 处理情况三
    // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
    getRemoveEdge(edges);
}

算法的时间复杂度和空间复杂度为O(N)。