leetcode_day58

今日内容：

• 冗余连接
• 冗余连接II

冗余连接

题目：

树可以看成是一个图（拥有 n 个节点和 n - 1 条边的连通无环无向图）。

现给定一个拥有 n 个节点（节点标号是从 1 到 n）和 n 条边的连通无向图，请找出一条可以删除的边，删除后图可以变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

思路：

并查集模板，直接套

代码

#include <bits/stdc++.h>
using namespace std;
class UnionFind{
public:
    vector<int> f;
    UnionFind(int n) {
        f.resize(n);
        for(int i = 0;i < n;i++) {
            f[i] = i;
        }
    }
    int find(int u) {
        if(u != f[u]) {
            f[u] = find(f[u]);
        }
        return f[u];
    }
    void join(int u, int v) {
        f[find(u)] = find(v);
    }
    bool isSame(int u, int v) {
        return find(u) == find(v);
    }
};

int main() {
    int N;
    cin >> N;
    UnionFind uf(N);
    for(int i =0;i < N;i++) {
        int a, b;
        cin >> a >> b;
        if(uf.isSame(a, b)) {
            cout << a << ' ' << b;
            return 0;
        }
        else uf.join(a, b);
    }
    return 0;
}

冗余连接II

题目：

有向树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有根树拥有 n 个节点和 n - 1 条边。

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表 s 节点有一条连接 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

思路：

个人错误思路

并查集本身也是有向的，可直接按顺序加入边来模拟建树，需要考虑以下两种非法情况：

1. 含圈：检查新加入的边两端是否同根 find(u) == find(v)，若相同，则删除该边
2. 入度大于1：检查新加入的边两端是否已经加入树中 u != find(u)，若不等，说明u已经在树中作为子，不可再作为子。

需要注意并查集加入边的顺序，输入2 1，则使f[1] = 2。

问题描述：

思路是错的，代码能过因为用例太弱。对于用例：

4
2 1
3 1
1 4
4 2

正解是删去2 1，若采用上面的思路，则遇到3 1时就会输出3 1，因为1已经被用过了，3 1和2 1肯定有一个会被删掉，删除靠后的3 1。

但整体来看，满足了入度条件却忽略了后面的圈条件，所以并不能按顺序模拟建树。

于是，我将入度非法的输出：

if(uf.isSame(a,b)) {//如果a -> b的b已经被占用
cout << a << ' ' << b;//按照题意，直接删去这条
return 0;
}

改为输出已被占用的子和对应的父：

if(uf.isVisited(b)) {//如果a -> b的b已经被占用
cout << uf.find(b) << ' ' << b;//输出之前输入的 占用b的边
return 0;
}

即当遇到3 1时，输出2 1，这显然违背了题意(输出靠后的边)，但是能AC，说明用例中只有这一个能够反按顺序建树的思路。

同类型用例可概括为"一个圈加圈外的一条指向圈的边"：

带尾巴的圈

输入时只需将圈外边先于整个圈输入即可越过检查，如：

5 | 1 2 | 2 3 | 5 3 | 4 1 | 3 4 |

图例

正解应该删去2 3，但我的代码输出3 1。将1 2和2 3交换顺序，则会输出1 3。(甚至路径压缩的错误都出来了……)

具体错误应该在于判断非法后默认输出当前边。自以为满足了靠后输出的要求，实际上却忽视了整体。应该像Carl那样判断应该删那一条边。

正确思路

代码随想录 | 冗余连接II

代码

错误代码：

#include <bits/stdc++.h>
using namespace std;
class UnionFind{//并查集类
public:
    vector<int> f;
    UnionFind(int n) {
        f.resize(n);
        for(int i = 0;i < n;i++) {
            f[i] = i;
        }
    }
    int find(int u) {
        if(u != f[u]) {
            return find(f[u]);
        }
        return f[u];
    }
    void join(int u, int v) {//u做根
        f[find(v)] = find(u);
    }
    bool isVisited(int v) {
        return v != find(v);
    }
    bool isSame(int u, int v) {
        return find(u) == find(v);
    }
};
 
int main() {
    int N;
    cin >> N;
    UnionFind uf(N + 1);
    for(int i = 0;i < N;i++) {
        int a, b;
        cin >> a >> b;
        if(uf.isSame(a,b)) {//判圈
            cout << a << ' ' << b;//有圈，直接删当前
            return 0;
        }
        else if(uf.isVisited(b)) {//判入度
            cout << uf.find(b) << ' ' << b;//有重，直接删当前的
            return 0;
        }
        else uf.join(a, b);
    }
    return 0;
}

carl哥的代码：

#include <iostream>
#include <vector>
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 vector<vector<int>>& 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 vector<vector<int>>& 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;
    vector<vector<int>> 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);
}